University of Guelph: CIS 3490 W25 – Final Exam with solutions, latest 2026 100% updated.

University of Guelph CIS 3490 W25 – Final Exam (April 12, 2:30 PM) Solutions Instructor: Joe Sawada and Daniel Gabri´c 1 1. Consider the following pseudocode given a two dimensional array G, and a list of integers stored in array A. 1: for i from 1 to n do 2: d ← 0 3: for j from i + 1 to n do d ← d + G[i][j] 4: Print(“The degree of i is d”) 5: MergeSort(A[i..n]) Let f(n) denote the number of steps carried out by this code in the worst case, as a function of the input n. What is the best upper bound for f(n)? (a) O(n log n) (b) O(n2) (c) O(n2 log n) (d) O(n3) (e) (none of the above) 2. Consider the following recursive algorithm where the input is an integer n and a set S = {s1, s2, . . . , sn} with n integers. 1: procedure Recursive(n, S) 2: if n = 1 then return 3: Recursive(n - 2,{s3, s4, . . . , sn}) 4: for i from 1 to n do Output si 5: if sn-1 sn then 6: Swap sn-1 and sn 7: Recursive(n - 1, {s1, s2, . . . , sn-1}) 8: else 9: Recursive(n - 1, {s1, s2, . . . , sn-1}) Let T(n) denote the running time of the above algorithm where T(1) = Θ(1). What is T(n) for n 1? (a) 2T(n - 1) + T(n - 2) (b) 2T(n - 1) + T(n - 2) + O(n2) (c) T(n - 1) + T(n - 2) + O(n) (d) T(n - 1) + T(n - 2) + O(1) 2 (e) (none of the above) 3. Consider a problem P. Suppose there exists an algorithm to solve P that runs in O(n2) time for every possible input. Then a lower bound for the problem P is (a) Ω(n2) (b) Θ(n2) (c) Θ(1) (d) There is not enough information to determine a lower bound (e) (none of the above) 4. Consider an implementation of QuickSort that uses a randomized pivot. What is an upper bound on the worst case and expected case of this algorithm? (a) O(n2) and O(n log n) (b) O(n2) and O(n2) (c) O(n log n) and O(n) (d) O(n log n) and O(n log n) (e) (none of the above) 5. Suppose you have a set of n integers in the range 1 to 143, 000 (roughly the population of Guelph). Suppose the values are not uniformly distributed. What is the best upper bound on the time required to sort these integers? (a) O(1) (b) O(log n) (c) O(n) (d) O(n log n) (e) (none of the above) Use a bucket sort, since there is a constant number of options. 6. What is the worst-case running time of randomized quick select and deterministic select, respectively, to find the k-th smallest value in a list of n numbers? (a) O(log n) and O(n) 3 (b) O(log n) and O(n log n) (c) O(n) and O(n) (d) O(n log n) and O(n) (e) (none of the above) 7. In a recursive implementation (no dynamic programming) of Pascal’s identity to compute C(n, k), how many times is C(4, 3) calculated with an initial call of C(7, 4)? (a) 1 (b) 2 (c) 3 (d) 4 (e) (none of the above) - similar to quiz 8. Which of the following is true regarding a Greedy algorithm? (a) it never backtracks and always finds an optimal solution, even if it takes exponential time (b) it never backtracks and always makes a choice that appears best at a given moment (c) it can backtrack if it reaches a dead end, but at each step it makes a choice that appears best at a given moment (d) it builds up a solution one step at a time until it finds an optimal solution (e) (none of the above) 9. In which situation should you consider applying a Dynamic programming solution? (a) if a problem has an iterative solution, but nested for loops lead to an inefficient algorithm (b) if a problem has a recursive formulation with overlapping subproblems (c) if every possible recursive solution to a problem runs in exponential time (d) if the problem requires computing a table of values (e) (none of the above) 4 10. The Master Theorem: (a) can be applied to prove a problem is NP-complete (b) can be applied to all divide and conquer algorithms to determine an upper bound on their running time (c) is a method for determining the asymptotic running time for all recursive algorithms (d) is a method for determining the asymptotic running time for some recursive algorithms (e) (none of the above) Consider the following directed graph for Questions 11 and 12. a b c d e f g 11. Which one of the following is NOT a valid ordering of the vertices if the graph was traversed using breadth-first search (BFS)? (a) c, d, e, f, g, b, a (b) d, c, f, g, e, a, b (c) b, g, c, f, a, d, e (d) f, c, g, b, e, d, a (e) e, c, f, d, b, g, a 12. Which one of the following is NOT a valid ordering of the vertices if the graph was traversed using depth-first search (DFS)? (a) a, b, g, f, c, d, e (b) d, e, f, c, g, a, b (c) d, e, f, c, g, b, a 5 (d) c, f, e, b, a, d, g (e) b, c, g, f, a, d, e 13. How many borders does the string abaababaaba have? (a) 2 (b) 3 (c) 4 (d) 5 (e) (none of the above) 14. Consider an unordered list S of n hockey players. With each player there is a corresponding statistic: the number of goals they have scored in their career. For your history assignment you want to study some slightly above average players. To do this, you want to find the ⌈log n⌉ who were closest to the player who ranks ⌈3n/4⌉ in the list. Since you took CIS 3490, you know that this can be done in: (a) O(1) time (b) O(log n) time (c) O(n) time (d) O(n log n) time (e) (none of the above) Apply Deterministic Select to find the player. Then subtract that number of goals from all players (taking absolute value). Then find the ⌈log n⌉ player from that list, and keep everyone with a smaller difference. 15. Find the adjacency matrix of the transitive closure of the graph defined by the following adjacency matrix:  1 0 1 0 1 0 1 1 0  (a)  1 1 1 0 1 0 1 1 1  6 (b)  1 0 1 0 1 0 1 1 1  (c)  1 0 1 0 1 0 1 1 0  (d)  1 1 1 0 1 0 1 1 0  (e) (none of the above) 16. The problem of multiplying two n × n matrices has worst-case running time that is (a) Θ(n3) (b) Θ(n2.8) (c) Θ(nlog 7) (d) O(nlog 7) (e) (none of the above) the upper bound is correct, though tighter upper bounds are known 17. Consider a sequence X of length n. A longest subsequence of X that is a palindrome (it reads the same forwards as backwards) can be found by computing the reverse of X, denoted XR, and then looking for a longest common subsequence in X and XR. This can be done by applying dynamic programming in: (a) O(1) time (b) O(n) time (c) O(n log n) time (d) O(n2) time (e) (none of the above) 18. Consider the following Directed Acyclic Graph (DAG). 7 a b c d Which one of the following is true? (a) c, b, a, d is the only topological ordering (b) both c, a, d, b and b, d, c, a are topological orderings (c) both c, b, a, d and b, c, a, d are topological orderings (d) the graph does not have any topological ordering (e) (none of the above) 19. Consider the scheduling problem discussed in class for the following 5 jobs with a deadline, profit, and duration (d, p, t): (1,2,1), (2,2,2), (2,4,1), (4,4,3), (5,1,1). What is the maximum profit of a feasible schedule of the 5 jobs finishing by time (overall deadline) 4? (a) 4 (b) 5 (c) 6 (d) 7 (e) (none of the above) 20. Recall the Prefer-0 greedy algorithm to construct a de Bruijn sequence. That algorithm depends on the starting seed to be 0n-1. Suppose for n = 3, the seed string is set to be 01. What is the result of applying the Prefer-0 greedy algorithm? In other words, what is the sequence of bits produced after the seed before terminating? (a) 0001101 (b) (c) (d) (e) (none of the above) 8 21. Suppose you are given a weighted directed graph with n vertices, Ω(n2) edges, and no negativeweight cycles. What procedure is the most appropriate and efficient at finding a shortest path between all pairs of vertices? (a) applying the Floyd-Warshall algorithm (b) applying the Bellman-Ford algorithm to every vertex (c) applying Dijkstra’s algorithm to every vertex (d) applying the shortest path algorithm for DAG’s to every vertex (e) (more than one of the above) 22. Network flow can be applied to solve the Maximum Matching Problem in a bipartite graph G = ((V1, V2), E). The corresponding flow network has (i) an edge from a source vertex s to every vertex in V1, (ii) the edges E directed from the vertices in V1 to V2, and (iii) an edge from every vertex from V2 to a sink vertex t. What are the weights on the edges in each group (i),(ii),(iii) required for this model? (a) 1, 1, 1 (b) ∞, 1∞ (c) 1, ∞, 1 (d) ∞, 1, 1 (e) (none of the above) 23. The Sports (baseball) Elimination Problem asks whether or not a sports team X still has a chance to win their division. This can be solved by modelling the problem to a network flow graph G. What is true about this mapping? (a) there is a vertex for every remaining game between any two teams in X’s division. (b) there is a vertex for every team in the division, except for X (c) every edge leaving the source has weight 1 (d) every edge coming into the sink has weight 1 (e) (none of the above) 9 24. What is the failure function f of the string abaababaaba? Note: The i’th term in a tuple represents f(i-1). (a) (0, 0, 1, 1, 2, 3, 2, 3, 4, 5, 6) (b) (0, 0, 1, 2, 2, 3, 2, 3, 4, 5, 6) (c) (0, 0, 0, 1, 2, 3, 2, 3, 4, 5, 6) (d) (0, 0, 1, 1, 2, 3, 4, 3, 4, 5, 6) (e) (none of the above) 25. Consider the following graph. a b c d 7 3 8 -11 e 4 2 1 10 What is the length of a shortest path from a to d? (a) -3 (b) -4 (c) -2 (d) -5 (e) (none of the above) 26. Which of the following is true regarding the theory of NP-completeness? (a) the theory demonstrates that some decision problems in NP cannot be solved in polynomial time (b) if there exists an NP-complete problem that can be solved in polynomial time, then all NP-complete problems and all problem in NP can be solved in polynomial time 10 (c) the decision problems 2-SAT, Euler cycle, 0-1 Knapsack, and Shortest Path are all NPcomplete problems (d) if you can demonstrate that a specific algorithm does not solve the Hamilton cycle decision problem in polynomial time, then P ̸= NP (e) (none of the above) 27. Suppose you are given a weighted directed acyclic graph (DAG) with n vertices, Θ(n) edges, and positive edge-weights. In the worse case, what procedure is the most appropriate and efficient at finding a shortest path between all pairs of vertices? (a) applying the Floyd-Warshall algorithm (b) applying the Bellman-Ford algorithm to every vertex (c) applying Dijkstra’s algorithm to every vertex (d) applying the shortest path algorithm for DAG’s to every vertex (e) (more than one of the above) 28. FreshBooks is interviewing n new co-op students this summer for 7n different positions. The process is as follows: each position ranks up to 10 students, and each student can rank up to n/2 positions. A hiring can take place for a given position if and only if a student has ranked the position and the position has ranked the student. The company would like to maximize the number of positions it fills. What algorithm should they apply, and what is a tight upper bound on the worst case running time? (a) DAG shortest path and O(n3) (b) Ford Fulkerson and O(n2) (c) Ford Fulkerson and O(n3) (d) Ford Fulkerson and O(n4) (e) (none of the above) This is bipartite matching on a graph where m = O(n), since there are at most 70n edges between the students and the position. Since the maximum matching is O(n), we require at most n iterations of Ford-Fulkerson. 11 Consider the following flow network G with flow f for Questions 29-31. s x t z 6/7 7/8 3/4 7/7 6/9 2/3 1/4 5/5 y 29. What is c(z, y) and f(z, y)? (a) 4 and 1 (b) 1 and 4 (c) -1 and -4 (d) 4 and -4 (e) (none of the above) 30. What is true about the residual graph Gf of G? (a) it contains no augmenting path (b) s, x, y, z, t is an augmenting path (c) the capacity cf(t, z) is 6 (d) the capacity cf(s, t) is always equal to the maximum flow (e) (none of the above) 31. What is true about the flow network G? (a) |f| = 13 and S = {s, x, y, t} and T = {z} is a valid cut in G (b) there is a cut in G that has capacity equal to |f| (c) the capacity of the cut c({s}, {x, y, z, t}) = 13 (d) if |f| is not maximal, then it is less than the capacity of every cut in G (e) (none of the above) 12 32. The Tolstoy classic War and Peace has 587,000 words. Every year, there is a competition to see whether or not a given phrase P is found in the book. Suppose the phrase P is composed of n words, where n 1000. What is a tight bound on the running time to answer this question in the worst case? (a) Θ(1) (b) Θ(log n) (c) Θ(n) (d) Θ(n log n) (e) (none of the above) Since the text is constant, and n 1000, this is considered to be a constant time problem. 33. Consider a complete weighted undirected graph G = (V, E) where V = {a, b, c, d, e, f}. The weights on the edges are as follows: w(a, b) = 3, w(a, f) = 7, w(b, f) = 8, w(c, d) = 2, w(c, f) = 1, w(d, e) = 6, w(d, f) = 4, w(e, f) = 5, and the rest of the edges have weight 100. What is the 4th edge added in the following two minimum spanning tree algorithms: Kruskal and Prim-Jarn´ık starting at vertex f? (a) (e, f) and (e, f) (b) (e, f) and (a, f) (c) (d, f) and (d, f) (d) (d, f) and (a, b) (e) (none of the above) 34. Consider the problem of determining whether or not an undirected graph has exactly one cycle (with at least three edges). Which algorithm can solve this problem with the best asymptotic running time for the worst case? (a) run the DAG shortest path algorithm and test for the number of cycles (b) run a DFS and count the number of back edges (c) run a BFS and count the number of back edges (d) give a unique weight to each edge and run Kruskal’s algorithm to detect the number of cycles (e) count to see if there are exactly n edges 13 35. Consider the following directed graph. a b c d e f h g i What is the number of strongly connected components in the graph? (a) 1 (b) 2 (c) 3 (d) 4 (e) (none of the above) the vertex e is one, and all the other vertices form another one 36. Let B = . What is the maximum discrepancy of B? And furthermore, what is the best lower bound to compute this value for an arbitrary binary string of length n? (a) 5 and Ω(n) (b) 4 and Ω(n) (c) 5 and Ω(n log n) (d) 4 and Ω(n log n) (e) (none of the above) 5 and it can be computed in linear time as in Ass 1 37. This pioneer in the field of algorithms specialized in network flow problems. He is also known for developing an algorithm to find shortest paths in graphs that have negative weights. (a) D. Fulkerson (b) E. Dijkstra (c) L. Ford 14 (d) R. Bellman (e) (none of the above) Ford 38. Consider the pattern P = abcba and text T = abbbccabbba. Suppose you are in the middle of executing the Boyer-Moore algorithm and it has just updated i and j to i = 4 and j = 4. According to the Boyer-Moore algorithm, what are i and j updated to in the next step? (a) i = 3 and j = 3 (b) i = 5 and j = 4 (c) i = 6 and j = 4 (d) i = 7 and j = 4 (e) (none of the above) 39. What is true about the 0-1 Knapsack problem with n items, where the i-th item has weight wi, and a knapsack with capacity C? (a) there is a known greedy algorithm to find an optimal solution that runs in O(n2) time (b) it can be solved with dynamic programming, but it is NP-complete (c) it can be solved with dynamic programming in O(n3) time (d) it is a special case of a scheduling problem, but there is no known algorithm that finds an optimal solution (e) (none of the above) 40. Suppose you are given a weighted undirected graph with n vertices, Θ(log(n)) edges, and positive edge-weights. Let u and v be two vertices in the graph. In the worst case, what algorithm is the most appropriate and efficient at finding a shortest path between u and v? (a) Floyd-Warshall algorithm (b) Bellman-Ford algorithm (c) Dijkstra’s algorithm (d) the shortest path algorithm for DAG’s (e) (more than one of the above) Solution: (e) Bellman-Ford and Dijkstra’s would both be O(n log n) 15 41. Given a sequence of numbers S = s1, s2, . . . , sn, a mode is a value that appears the most number of times in this sequence. Which technique can be applied to accurately determine a mode of S with the given running time for the worst case? (a) apply a hash table in O(n) time (b) apply QuickSort with a randomized select in O(n log n) time (c) apply a stable BucketSort in O(n) time (d) apply a weighted median approach in O(n) time (e) (none of the above) about the possible input. A hash table will require O(n2) time in the worst case. QuickSort also requires O(n2) in the worst case unless it applies the Deterministic Select. The best is to sort with any O(n log n) sorting algorithm and then scan the list. 42. Consider the following weighted directed graph. 8 6 2 1 4 2 3 7 5 a 1 b f d c e Suppose we execute Dijkstra’s algorithm on this graph, with source vertex a. What is the fourth vertex removed from the Priority Queue? (a) b (b) c (c) d (d) e (e) f – END OF FINAL EXAM – 16