Midterm2_Solution_311

COMPSCI 311: Introduction to Algorithms Second Midterm Exam — SOLUTIONS October 25, 2023 Name: ID: Instructions: • Answer the questions directly on the exam pages. • Show all your work for each question. Providing more detail including comments and expla- nations can help with assignment of partial credit. • If you need extra space, use the blank pages at the end of the exam. • No books, notes, calculators or other electronic devices are allowed. Any cheating will result in a grade of 0. • If you have questions during the exam, raise your hand. 1

Question 1. ( 4 points ) Topological orderings. List all possible topological orderings for this graph. Solution: a, b, c, d, e, f a, b, d, c, e, f a, b, d, e, c, f a, d, b, c, e, f a, d, b, e, c, f Question 2. ( 5 points ) You are given n numbers and want to order them as v 1 , v 2 , . . . , v n so the value of the ordering, defined as follows, is as small as possible: value of ordering = v 1 + 2 v 2 + 3 v 3 + . . . + nv n 2.1 ( 1 points ): Suppose the numbers are 1, 2, and 5, and are ordered as v 1 = 5 , v 2 = 1 , v 3 = 2 . What is the value of this ordering? Solution: The value is 5 + 2 · 1 + 3 · 2 = 13. Claim : The value is minimized by any non-increasing ordering, i.e., whenever v 1 ≥ v 2 ≥ . . . ≥ v n . Proof : Suppose for contradiction that some ordering v 1 , . . . , v n minimizes v 1 +2 v 2 +3 v 3 + . . . + nv n but does not satisfy v 1 ≥ v 2 ≥ . . . ≥ v n . Then there is some index i such that v i < v i +1 . Then ... 2.2 ( 4 points ): Complete the proof by arguing that the ordering v 1 , . . . , v n does not have minimum value, a contradiction. Solution: Consider swapping the numbers in positions i and i + 1 to get a new ordering. The original value minus the new value is h iv i + ( i + 1) v i +1 i − h iv i +1 + ( i + 1) v i i = v i +1 − v i > 0 Therefore, the new values is smaller, which contradicts our assumption that the ordering was optimal. 2

Question 4. ( 6 points ) We are given a connected, undirected graph with m edges and n nodes where each edge has weight 1 or 2. A student proposes the following O ( m + n ) time algorithm to find the MST. Replace each weight-2 edge by a two-edge path of weight-1 edges. Now the resulting graph has all edges of weight 1, and we know any spanning tree is an MST, so we return a BFS tree of the new graph. 4.1 ( 3 points ): Does this give us an MST of the original graph? Briefly explain. Solution: No. This construction seems like it may be useful but it doesn’t preserve information about spanning trees in the original graph. For example, the BFS tree might only include “half” of an edge of the original graph. Specifically, suppose the original graph is a tree specific example: if the original graph consists only of two edges ( a, b ) and ( b, c ) of weight 2. 4.2 ( 3 points ): Does this run in O ( m + n ) time, whether it is correct or not? Briefly explain. Solution: Yes, it does. The running time is O ( m ′ + n ′ ) where m ′ and n ′ are the numbers of edges and nodes, respectively, in the new graph. We have m ′ ≤ 2 m and n ′ ≤ n + m , so m ′ + n ′ ≤ 3 m + n , which means O ( m ′ + n ′ ) = O ( m + n ). 4

Question 5. ( 13 points ) Consider this graph when answering the following questions: s a b c d e 3 8 3 5 4 2 1 2 5.1 ( 1 points ): What is the total cost of a minimum spanning tree (MST)? 13 5.2 ( 3 points ): List the weights of the edges added by Kruskal’s algorithm in the order they are added. 1, 2, 3, 3, 4 5.3 ( 2 points ): How many different minimum spanning trees are there? 2. The weights are 1, 2, 2, 3, 4. Either edge of weight 2 can be used. 5.4 ( 3 points ): List the nodes that are attached by Prim’s algorithm starting from s . a, b, d, e, c 5.5 ( 3 points ): List the first three nodes after s that are explored by Dijkstra’s algorithm starting from s . a, b, c 5.6 ( 1 points ): What is the length of the shortest path from s to e ? 10 5

Question 7. ( 12 points ) Follow the instructions to solve the recurrences. You need to show the steps in your answer. Final answer is not sufficient. 7.1 ( 3 points ): Consider the recurrence T ( n ) = T ( n − 1) + n 2 . Use unrolling to solve this recurrence. What answer do you get? (a) Θ(log n ) (b) Θ( n ) (c) Θ( n 2 ) (d) Θ( n 3 ) Solution: The exact answer is T ( n ) = ∑ n i =1 i 2 , which solves to Θ( n 3 ). 7.2 ( 3 points ): Consider the recurrence T ( n ) = 4 T ( n/ 2) + O ( n 3 ) . Solve this recurrence using any technique. (Hint: try the master theorem). (a) Θ( n 2 ) (b) Θ( n 2 log n ) (c) Θ( n 3 ) (d) Θ( n 3 log n ) Solution: Case 1 of the master theorem would give Θ( n 3 ) and Case 3 would give Θ( n log 2 4 ) = Θ( n 2 ). Since the former is larger, the answer is Θ( n 3 ). 7.3 ( 3 points ): Consider the recurrence T ( n ) = 8 T ( n/ 2) + O ( n 3 ) . Solve this recurrence using any technique. (Hint: try the master theorem). (a) Θ( n 2 ) (b) Θ( n 2 log n ) 7

(c) Θ( n 3 ) (d) Θ( n 3 log n ) Solution: Case 1 of the master theorem would give Θ( n 3 ) and Case 3 would give Θ( n log 2 8 ) = Θ( n 3 ). Since these two are equal, the answer comes from Case 2 of the Master theorem, and is Θ( n 3 log n ). 7.4 ( 3 points ): Consider the recurrence T ( n ) = 4 T ( n/ 3) + O ( n 1 / 2 ) . Solve this recurrence using any technique. (Hint: try the master theorem). (a) Θ( n 1 / 2 ) (b) Θ( n 1 / 2 log n ) (c) Θ( n log 3 4 ) (d) Θ( n log 3 4 log n ) Solution: Case 1 of the master theorem would give Θ( n 1 / 2 ) and Case 3 would give Θ( n log 3 4 ). Since the latter is larger, the answer is Θ( n log 3 4 ). 8

Question 9. ( 9 points ) During your time-travels you collect a record of bitcoin prices for the next n years, which you plan to use to get rich. The price in dollars in year i is p ( i ). Your plan is to find the two years i and j such that i < j and the difference p ( j ) − p ( i ) is as large as possible, and buy in year i and sell in year j . 9.1 ( 2 points ): Suppose n = 4 and p (1) = 3 , p (2) = 1 , p (3) = 4 , p (4) = 5 . What years will you select in this example? i = 2 j = 4 Toward an Algorithm. Consider the following outline for a divide-and-conquer algorithm to solve the problem. Assume that n is a power of 2, and, for simplicity, your algorithm will return only the maximum value of p ( j ) − p ( i ), and not the years themselves. Divide. Let L = { 1 , ..., n/ 2 } and R = { n/ 2 + 1 , ..., n } . Conquer — Recursively find δ L , the biggest increase p ( j ) − p ( i ) for i, j ∈ L — Recursively find δ R , the biggest increase p ( j ) − p ( i ) for i, j ∈ R Combine. Use δ L , δ R , and some additional computation to compute and return δ , the biggest increase p ( j ) − p ( i ) for i, j ∈ { 1 , . . . , n } . 9.2 ( 2 points ): Assume the combine step is implemented to take O ( n ) time, and let T ( n ) be the running time of this algorithm on an input of size n . Write a recurrence for T ( n ) . Solution: T ( n ) = 2 T ( n/ 2) + O ( n ). Variations such as T ( n ) ≤ 2 T ( n/ 2) + cn are also fine. 9.3 ( 2 points ): Solve your recurrence to give a simple expression for T ( n ) . Solution: O ( n log n ) 9.4 ( 3 points ): Describe how to implement the combine step in O ( n ) time. Solution: Find the biggest increase p ( j ) − p ( i ) where i ∈ L and j ∈ M . Do this by letting p ( i ) be the minimum price for all years i ∈ L , and letting p ( j ) be the maximum price for all years j ∈ R . Call the resulting value δ M . Return the maximum of δ L , δ R , δ M . 10