6.046J Spring 2012 Quiz 1 Solutions

Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Dana Moshkovitz and Bruce Tidor March 6, 2012 6.046J/18.410J Quiz 1 Solutions Quiz 1 Solutions 28 21 14 7 0 21-25 26-30 31-35 36-40 41-45 46-50 51-55 56-60 61-65 66-70 71-75 76-80 Mean: 58; Median: 60; Standard deviation: 12 6.046J/18.410J Quiz 1 Solutions Name 2 Problem 0. Name. [1 point] Write your name on every page of this exam booklet! Don’t forget the cover. Problem 1. True or False. [24 points] (8 parts) Circle T or F for each of the following statements to indicate whether the statement is true or false, and briefly explain why. Your justification is worth more points than your true-or-false designation. √ 2 (a) T F The solution to the recurrence T (n) = 2n T (n − 1) is T (n) = Θ(( 2)n +n ). (Assume T (n) = 1 for n smaller than some constant c). Solution: [3 points] True. Let T (0) = 1. Then T (n) = 2n · 2n−1 · 2n−2 . . . 21 = 2(n+(n−1)+(n−2)+...+1) . √ 2 P 2 Because ni=1 i = n(n + 1)/2, we therefore have T (n) = 2(n +n)/2 = ( 2)n +n . Some students also correctly solved the problem by using the substitution method. Some students made the mistake of multiplying the exponents instead of adding 2 2 them. Also, it has to be noted that 2n /2 6= Θ(2n ). (b) T F The solution to the recurrence T (n) = T (n/6) + T (7n/9) + O(n) is O(n). (Assume T (n) = 1 for n smaller than some constant c). Solution: [3 points] True. Using the substitution method: T (n) ≤ cn/6 + 7cn/9 + an ≤ 17cn/18 + an ≤ cn − (cn/18 − an) This holds if c/18 − a ≥ 0, so it holds for any constant c such that c ≥ 18a. Full credit was also given for solutions that uses a recursion tree, noting that the total work at level i is (17/18)i n, which onverges to O(n). 6.046J/18.410J Quiz 1 Solutions Name (c) T F In a simple, undirected, connected, weighted graph with at least three vertices and unique edge weights, the heaviest edge in the graph is in no minimum spanning tree. Solution: [3 points] False. If the heaviest edge in the graph is the only edge connecting some vertex to the rest of the graph, then it must be in every minimum spanning tree. (d) T F The weighted task scheduling problem with weights in the set {1, 2} can be solved optimally by the same greedy algorithm used for the unweighted case. Solution: [3 points] False. The algorithm will fail given the set of tasks (given in the form ((si , fi ), wi ): {((0, 1), 1), ((0, 2), 2)}. (e) T F Two polynomials p, q of degree at most n − 1 are given by their coefficients, and a number x is given. Then one can compute the multiplication p(x) · q(x) in time O(log n). Solution: [3 points] False. We need at least Θ(n) time to evaluate each polynomial on x and to multiply the results. Some students argued incorrectly that it must take O(n log n) using FFT, but FFT overkills because it computes all coefficients, not just one. 3 6.046J/18.410J Quiz 1 Solutions Name 4 (f) T F Suppose we are given an array A of n distinct elements, and we want to find n/2 elements in the array whose median is also the median of A. Any algorithm that does this must take Ω(n log n) time. Solution: [3 points] False. It’s possible to do this in linear time using S ELECT : first find the median of A in Θ(n) time, and then partition A around its median. Then we can take n/4 elements from either side to get a total of n/2 elements in A whose median is also the median of A. (g) T F There is a density 0 < ρ < 1 such that the asymptotic running time of the FloydWarshall algorithm on graphs G = (V, E) where |E| = ρ |V |2 is better than that of Johnson’s algorithm. Solution: [3 points] False. The asymptotic running time of Floyd-Warshall is O(V 3 ), which is at best the same asymptotic running time of Johnson’s (which runs in O(V E + V log V ) time), since E = O(V 2 ) (h) T F Consider the all pairs shortest paths problem where there are also weights on the vertices, and the weight of a path is the sum of the weights on the edges and vertices on the path. Then, the following algorithm finds the weights of the shortest paths between all pairs in the graph: APSP-W ITH -W EIGHTED -V ERTICES (G, w): 1 for (u, v) ∈ E 2 Set w ′(u, v) = (w(u) + w(v))/2 + w(u, v) 3 Run Johnson’s algorithm on G, w ′ to compute the distances δ ′ (u, v) for all u, v ∈ V . 4 for u, v ∈ V 5 Set duv = δ ′ (u, v) + 21 (w(u) + w(v)) 6.046J/18.410J Quiz 1 Solutions Name 5 Solution: [3 points] True. Any shortest path from u to v in the original graph is still a shortest path in the new graph. For some path {v0 , v1 , . . . , vk }, we have: ′ w (v0 ❀ vk ) = = = k−1 X i=0 k−1 X i=0 k−1 X i= 0 ((w(vi ) + w(vi+1 ))/2 + w(vi , vi+1 )) 1 w(vi , vi+1 ) + 2 w(vi , vi+1 ) + k X i=0 k −1 X w(vi ) + i=0 k X i=1 w(vi ) ! 1 w (vi ) − (w(v0 ) + w(vk )) 2 1 = w(v0 ❀ vk ) − (w(v0 ) + w(vk )) 2 Therefore, the order of all paths from v0 to vk remains unchanged so Johnson’s algorithm in line 3. finds the correct path, and the adjustment in line 5 finds the correct length dv0 vk . 6.046J/18.410J Quiz 1 Solutions Name 6 Problem 2. Translation [25 points] (5 parts) You have been hired to manage the translation process for some documentation. Unfortunately, different sections of the documentation were written in different languages: n languages in total. Your boss wants the entire documentation to be available in all n languages. There are m different translators for hire. Some of those translators are volunteers that do not get any money for their services. Each translator knows exactly two different languages and can translate back and forth between them. Each translator has a non-negative hiring cost (some may work for free). Unfortunately, your budget is too small to hire one translator for each pair of languages. Instead, you must rely on chains of translators: an English-Spanish translator and a Spanish-French translator, working together, can translate between English and French. Your goal is to find a minimum-cost set of translators that will let you translate between every pair of languages. We may formulate this problem as a connected undirected graph G = (V, E) with non-negative (i.e., zero or positive) edge weights w. The vertices V are the languages for which you wish to generate translations. The edges E are the translators. The edge weight w(e) for a translator e gives the cost for hiring the translator w(e). A subset S ⊆ E of translators can be used to translate between a, b ∈ V if and only if the subgraph GS = (V, S) contains a path between a and b. The set S ⊆ E is a translation network if and only if S can be used to translate between all pairs a, b ∈ V . (a) Prove that each minimum spanning tree of G is also a minimum-cost translation network. Solution: [5 points] Let T be some minimum spanning tree of G. Because T is a spanning tree, there is a path in T between any pair of vertices. Hence, T is a translation network. For the sake of contradiction, suppose that T is not a minimum-cost translation network. Then there must be some translation network S with total cost strictly smaller than T . Because S connects every pair of vertices, it must have some spanning tree T ∗ as a subgraph. Because all edge weights are nonnegative, we have w(T ∗) ≤ w(S) < w(T ). Hence, T is not the minimum spanning tree. This contradiction means that all spanning trees are also minimum-cost translation networks. 6.046J/18.410J Quiz 1 Solutions Name 7 (b) Give an example of a minimum-cost translation network that is not a minimum spanning tree of G. Solution: [5 points] If the graph of translators contains a cycle of translators all willing to work for $0, then it is possible to hire all of the translators in the cycle without increasing the overall cost of the translation network. The smallest example of this is the following: A $0 $0 B C $0 All three MSTs of the graph have total cost $0, so any translation network of cost $0 has minimum cost. Hence, we can take all translators in the cycle to get a minimumcost translation network that is not an MST. (c) Give an efficient algorithm that takes G as input, and outputs a minimum-cost translation network of G. State the runtime of your algorithm in terms of the number of languages n and the number of potential translators m. Solution: [5 points] We saw in part (a) that every minimum spanning tree is a minimum-cost translation network of G. Hence, to find a minimum-cost translation network, it is sufficient to find a minimum spanning tree of G. We may do so using Kruskal’s algorithm, for a runtime of Θ(m log n), or using Prim’s algorithm, for a runtime of Θ(m + n log n). 6.046J/18.410J Quiz 1 Solutions Name 8 Your bosses have decided that the previous approach to translation doesn’t work. When attempting to translate between Spanish and Portuguese — two relatively similar languages — it degrades the translation quality to translate from Spanish to Tagalog to Mandarin to Portuguese. There are certain clusters of languages that are more closely related than others. When translating between two languages that lie within the same cluster, such as Spanish and Portuguese, the translation is of high quality when the sequence of languages used to translate between them is completely contained within the cluster. More formally, the language set V can be divided into disjoint clusters C1 , . . . , Ck . Each cluster Ci contains languages that are fairly similar; each language is contained in exactly one cluster. Your bosses have decided that a translation between a, b ∈ Ci is high-quality if and only if all of the languages used on the path from a to b are also in Ci . The translator set S is a high-quality translation network if and only if it is a translation network, and for any language cluster Ci and any languages a, b ∈ Ci , S can be used for a high-quality translation between a and b. (d) Suppose that S is a minimum-cost high-quality translation network. Let Si = S ∩ (Ci × Ci ) be the part of the network S that lies within the cluster Ci . Show that Si is a minimum-cost translation network for the cluster Ci . Solution: [5 points] Let Si∗ be a minimum-cost translation network for Ci . Because S is a high-quality translation network, Si must contain a path between every pair of nodes in Ci , so Si is a translation network for Ci . For the sake of contradiction, assume that Si is not minimum-cost. Then w(Si ) > w(Si∗). Consider the translation network S ∗ = (S − Si ) ∪ Si∗ . Then w(S ∗) = w(S) − w(Si ) + w(Si∗ ) < w(S). Because Si∗ is a translation network of Ci , replacing Si with Si∗ will not disconnect any pair of vertices in the graph. Furthermore, any pair of vertices connected by a path in S that lay inside a particular cluster will be connected by a path in S ∗ that lies within the same cluster. Hence, S ∗ is a high-quality translation network with cost strictly less than S. This contradicts the definition of S, so Si must be a minimum-cost translation network. (e) Give an efficient algorithm for computing a minimum-cost high-quality translation network. Analyze the runtime of your algorithm in terms of the number of languages n and the number of translators m. Solution: [5 points] The idea behind this algorithm is to first compute one MST for each individual cluster, and then to compute a global MST using the remaining edges. More specifically, we do the following: 1. For each edge (u, v), if there is some cluster Ci such that u, v ∈ Ci , then add (u, v) to the set Ei . Otherwise, add (u, v) to the set Eglobal . 6.046J/18.410J Quiz 1 Solutions Name 9 2. For each cluster Ci , run Kruskal’s algorithm on the graph (Ci , Ei ) to get a minimumcost translation network Ti for the cluster. Take the union of these minimum to get a forest T . 3. Construct an empty graph Gglobal on nodes {1, . . . , k}. For each edge (u, v) in Eglobal , where u ∈ Ci and v ∈ Cj , check whether the edge (i, j) is in the graph Gglobal . If so, set w(i, j) = min{w(i, j), w(u, v)}. Otherwise, add the edge (i, j) to the graph Gglobal . In either case, keep a mapping source(i, j) = (u∗ , v ∗) such that w(i, j) = w(u∗ , v ∗). 4. Run Kruskal’s algorithm on the graph Gglobal to get Tglobal . 5. For each edge (i, j) ∈ Tglobal add the edge source(i, j) to T . We begin by examining the runtime of this algorithm. The first step requires us to be able to efficiently discover the cluster Ci that contains each vertex, which can be precomputed in time Θ(m) and stored with the vertices for efficient lookup. So this filtering step requires Θ(1) lookup per edge, for a total of Θ(m) time. The second step is more complex. We run Kruskal’s algorithm on each individual cluster. So for the cluster Ci , the runtime is Θ(|Ei | lg |Ci !). The total runtime here is: k X i=1 a · |Ei | lg |Ci | ≤ k X i=1 a · |Ei | lg n = (a lg n) k X i=1 |Ei | ≤ am lg n Hence, the total runtime for this step is Θ(m lg n). The third step also requires care. We can store the graph to allow us to efficiently lookup w(·, ·) and to tell whether an edge (i, j) has been added to the graph. We can also store source(·, ·) to allow for Θ(1) lookups. So the runtime here is bounded by Θ(m). The fourth step is Kruskal’s again, only once, on a graph with ≤ n vertices and ≤ m edges, so the total runtime is Θ(m lg n). The final step involves a lookup for each edge (i, j) ∈ T , for a total runtime of Θ(k) ≤ Θ(n). Hence, the runtime is dominated by the two steps involving Kruskal. So the total worst-case runtime is Θ(m lg n). Next we consider the correctness of this algorithm. Suppose that the result of this process is not the minimum-cost high-quality translator network. Then there must be a high-quality translator network S that has strictly smaller cost. Because S is a minimum-cost high-quality translator network, we know that the portion of S contained in the cluster Ci is a minimum-cost translator network for Ci , which has the same cost as the minimum spanning tree for that cluster computed in step 2 of the algorithm. So the total weight of all inter-cluster edges in S must be strictly less than the total weight of all inter-cluster edges in T . But the set of all inter-cluster edges in T formed a minimum spanning tree on the cluster, so any strictly smaller set of edges cannot span the set of all clusters. So S cannot be a translation network. This contradicts our assumption, and so T must be a minimum-cost high-quality translation network. 6.046J/18.410J Quiz 1 Solutions Name 10 Problem 3. All Pairs Shortest Red/Blue Paths. [18 points] (3 parts) R You are given a directed graph G = (V, E) with edge weights w : E → . In addition, each edge of the graph is either red or blue. The shortest red/blue path from vertex i ∈ V to vertex j ∈ V is defined as the shortest path from i to j among those paths that go through exactly one red edge (if there are no such paths, the length of the shortest red/blue path is ∞). We can represent this graph with two n × n matrices of edge weights, Wr and Wb , where Wr contains the weights of all red edges, and Wb contains the weights of all blue edges. (a) Given the Floyd-Warshall algorithm below, how would you modify the algorithm to obtain the lengths of the shortest paths that only go through blue edges? F LOYD -WARSHALL (W ): 1 n = W.rows 2 D (0) = W 3 for k = 1 to n (k) 4 let D (k) = (dij ) be a new n × n matrix 5 for i = 1 to n 6 for j = 1 to n (k) (k −1) (k−1) (k −1) 7 dij = min(dij , dik + dkj ) 8 return D (n) Solution: [6 points] In order to find shortest paths going through only blue edges, it suffices to ignore the red edges and run Floyd-Warshall on only the blue edges of the graph. We make the following changes: • Replace each occurrence of W with Wb in lines 1 and 2. (k) • Replace the matrices D (k) with blue versions Db in lines 2, 4, and 8. (k) (k) • Replace the matrix elements dij with blue versions db,ij in lines 4 and 7. While the second and third changes above are unnecessary for this part, they lay the groundwork for future parts below. 6.046J/18.410J Quiz 1 Solutions Name 11 (b) How would you modify your algorithm from part (a) to keep track not only of shortest paths with only blue edges, but also those with exactly one red edge, and to output the lengths of the shortest red/blue paths for all pairs of vertices in this graph? (k) Solution: [6 points] Add a new set of matrices Dr that give lengths of shortest paths with exactly one red edge and intermediate vertices up to k. The resulting pseudocode is as follows: R ED -B LUE -F LOYD -WARSHALL (Wr , Wb ): 1 n = Wr .rows (0) 2 Db = Wb (0) 3 Dr = Wr 4 for k = 1 to n (k) (k) (k) (k) 5 let Db = (db,ij ), Dr = (dr,ij ) be new n × n matrices 6 for i = 1 to n 7 for j = 1 to n (k) (k−1) (k −1) (k −1) 8 db,ij = min(db,ij , db,ik + db,kj ) (k) (k−1) (k−1) (k−1) (k−1) (k−1) 9 dr,ij = min(dr,ij , dr,ik + db,kj , db,ik + dr,kj ) (n) 10 return Dr 6.046J/18.410J Quiz 1 Solutions Name (c) Prove the correctness of your algorithm using a loop invariant. Solution: [6 points] The procedure for keeping track of paths that go through only blue edges is exactly equivalent to running Floyd-Warshall on the subgraph that con(k) tains only the blue edges of G, which is sufficient to show the correctness of Db for all k. Loop invariant: at the end of every iteration of the for loop from k = 1 to n, we have both the length of the shortest path for every pair (i, j) going through only blue edges and the length of the shortest path for every pair (i, j) going through exactly one red edge, in each using intermediate vertices only up to k. Initialization: At initialization k = 0, there are no intermediate vertices. The only blue paths are blue edges, and the only paths with exactly one red edge (red/blue paths) are red edges, by definition. Maintenance: Each iteration gets the shortest blue-edges-only path going from i to j using intermediate vertices up through k accurately, due to the correctness of the Floyd-Warshall algorithm. For the paths including exactly one red edge, for a given pair (i, j), there are two cases: either the shortest red/blue path from i to j using intermediate vertices through k does not go through k, or it does. If it does not go through k, then the length of this path is (k −1) equal to dr,ij . If it does go through k, then the red edge on this path is either between i and k or between k and j. Because of the optimal substructure of shortest paths, we can therefore break this case down into two subcases: the shortest path length is (k −1) (k −1) (k −1) (k −1) equal to min(dr,ik + db,kj , db,ik + dr,kj ). Line 9 in the algorithm above finds the minimum path length of these three different possibilities, so this iteration must find the shortest path length from i to j going through exactly one red edge, using only intermediate vertices through k. Termination: After n passes through the loop, all paths with intermediate vertices up to n have been included, and as there are only n vertices, shortest paths using all vertices as intermediates will be discovered. 12 6.046J/18.410J Quiz 1 Solutions Name 13 Problem 4. Telephone Psetting. [12 points] (3 parts) Upon realizing that it was 8:30 PM on Wednesday and he had not yet started his 6.046 pset, Ben Bitdiddle found n − 1 other students (for a total of n students) in the same situation, and they decided to do the pset, which coincidentally had n problems in total, together. Their brilliant plan for finishing the pset in time was to sit in a circle and assign one problem to each student, so that for i = 0, 1, . . . , n−1, student i did problem number i, and wrote up a solution for problem i meriting p(i) points. Then, they each copied the solutions to all the other problems from the student next to them, so that student i was copying from student i − 1 (and student 0 was copying from student n − 1). Unfortunately, they were in such a hurry that the copying chain degraded the quality of the solutions: by the time student i’s solution to problem i reached student j, where d = j − i (mod n), 1 d ∈ {0, 1, . . . , n − 1}, the solution was only worth d+1 p(i) points. (a) Write a formula that describes the total pset score S(x) for student x, where the total pset score is the sum of the scores that student x got on each of the n problems. Solution: [3 points] S(x) = n−1 X i=0 1 · p(i) ((x − i) mod n) + 1 Alternatively, it is also correct to give the equivalent sum: n−1 X 1 S(x) = · p((x − i) mod n) i+1 i=0 (b) Describe a simple O(n2 ) algorithm to calculate the pset scores of all the students. Solution: [3 points] Use the formula given in part (a) to calculate each student’s score. Because calculating the score requires summing n numbers, it takes O(n) time to calculate a single score, and therefore O(n2 ) time to calculate all the scores. (c) Describe a O(n log n) algorithm to calculate the pset scores of all the students. Solution: [6 points] The formula in the solution to part (a) describes a convolution: 1 letting g(y) = y+1 , the formula in part (a) can be written as S : n → , where P S(x) = i∈Zn p(i)g(x − i) = (p ⊗ g)(x). The algorithm is as follows: Z R 1. Apply FFT on p and g to get p̂ and ĝ (time Θ(n log n)). 2. Compute the transformed convolution Ŝ = p̂ · ĝ (time Θ(n)). 3. Apply the inverse FFT to get back the convolution S (time Θ(n log n)). 6.046J/18.410J Quiz 1 Solutions Name Alternatively, define two polynomials: 2n−1 n−1 X X i P1 (x) = p(i mod n)x and P2 (x) = 1 i x . Then student j’s pset score is i+1 i=0 i=0 equal to the coefficient of xn+j in the product of the polynomials P1 and P2 . Because we are multiplying two polynomials of degree at most 2n − 1, we can apply the polynomial multiplication method seen in class, which is outlined above: apply the FFT to get the evaluations of P1 and P2 on the roots of unity of order 2n, pointwise multiply, and finally apply the inverse FFT to get the coefficients of the product. 14