Class on Design and Analysis of Algorithms, Solutions to Final Exam

May 23, 2015 6.046J/18.410J Final Solutions Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Erik Demaine, Srini Devadas, and Nancy Lynch Final Solutions • Do not open this exam booklet until you are directed to do so. Read all the instructions first. • The exam contains 10 problems, with multiple parts. You have 180 minutes to earn 180 points. • This exam booklet contains 20 pages, including this one. '' • This exam is closed book. You may use three double-sided letter (8 12 × 11'' ) or A4 crib sheets. No calculators or programmable devices are permitted. Cell phones must be put away. • Do not waste time deriving facts that we have studied. Just cite results from class. • When we ask you to “give an algorithm” in this exam, describe your algorithm in English or pseudocode, and provide a short argument for correctness and running time. You do not need to provide a diagram or example unless it helps make your explanation clearer. • Do not spend too much time on any one problem. Generally, a problem’s point value is an indication of how many minutes to spend on it. • Show your work, as partial credit will be given. You will be graded not only on the correct­ ness of your answer, but also on the clarity with which you express it. Please be neat. • Good luck! Q Title Points Parts 1 True or False 56 2 Überstructure 3 Q Title 14 6 10 1 Meancorp 15 4 Forgetful Forrest 5 Piano Recital Name: Grade Points Parts Be the Computer 14 3 7 Startups are Hard 20 3 2 8 Load Balancing 15 2 15 3 9 Distributed Coloring 20 3 15 3 Total 180 Grade 6.046J/18.410J Final Solutions Name 2 Problem 1. True or False. [56 points] (14 parts) Circle T or F for each of the following statements to indicate whether the statement is true or false and briefly explain why. (a) T F [4 points] Suppose algorithm A has two steps, and A succeeds if both the steps succeed. If the two steps succeed with probability p1 and p2 respectively, then A succeeds with probability p1 p2 . Solution: False. Unless the two steps are independent. (b) T F [4 points] If the divide-and-conquer convex hull algorithm (from Lecture 2) used a Θ(n2 ) strategy to discover the maximum and minimum tangents, the overall algorithm would run in Θ(n2 log n) time. Solution: False. The recurrence would be T (n) = 2T ( n2 ) + Θ(n2 ) whose solu­ tion is T (n) = Θ(n2 ). (c) T F [4 points] In order to get an expected Θ(n log n) runtime for “paranoid” quick­ sort (from Lecture 3), we require the recursive divide step to split the array into two subarrays each of at least 14 the size of the original array. Solution: False. As long as it is a constant fraction of the original array, we can get the bound. (d) T F [4 points] A binary min-heap with n elements supports I NSERT in O(log n) amortized time and D ELETE -M IN in 0 amortized time. Solution: True. Same amortization as in class for insert/delete in 2-3 trees. 6.046J/18.410J Final Solutions Name (e) T F [4 points] The hash family H = {h1 , h2 } is universal, where h1 , h2 : {1, 2, 3} → {0, 1} are defined by the following table: h1 h2 1 2 3 0 1 0 1 0 1 (For example, h1 (3) = 0.) Solution: False. Consider elements 1 and 3: h1 and h2 both cause a collision between them, so in particular a uniformly random hash function chosen from H causes a collision between 1 and 3 with probability 1, greater than the 1/2 allowed for universal hashing (since there are 2 hash buckets). (f) T F [4 points] Recall the O(n3 lg n) matrix-multiplication algorithm to compute shortest paths, where we replaced the matrix-multiplication operator pair (∗, +) with (+, min). If we instead replace the operator pair with (+, ∗), then we com­ pute the product of the weights of all paths between each pair of vertices. Solution: False. If the graph has a cycle, there are infinitely many paths be­ tween some pairs of vertices, so the product ought to be ±∞, yet the matrixmultiplication algorithm will compute finite values if the original matrix has all finite values (e.g., a clique). (g) T F [4 points] Negating all the edge weights in a weighted undirected graph G and then finding the minimum spanning tree gives us the maximum-weight spanning tree of the original graph G. Solution: True. (h) T F [4 points] In a graph with unique edge weights, the spanning tree of secondlowest weight is unique. Solution: False, can construct counter-example. 3 6.046J/18.410J Final Solutions (i) T F Name 4 [4 points] In the recursion of the Floyd–Warshall algorithm: (k−1) (k−1) d(k) , duk uv = min{duv (k−1) + dkv }, (k) duv represents the length of the shortest path from vertex u to vertex v that con­ tains at most k edges. (k) Solution: False. duv is the length of the shortest path from vertex u to vertex v that only uses vertex {1, 2, · · · k} as intermediate nodes. (j) T F [4 points] Consider a network of processes based on an arbitrary undirected graph G = (V, E) with a distinguished vertex v0 ∈ V . The process at each vertex v ∈ V starts with a positive integer xv . The goal is for the process at v0 to compute the maximum maxv∈V xv . There is an asynchronous distributed algorithm that solves this problem using O(diam 2 d) time and O(E + diam · n) messages. Solution: True. Using the algorithm from Problem 10-2, we can construct a BFS tree rooted at v0 within the given time and message bounds. The root process can broadcast a signal telling all the processes that the tree is completed. Then the processes can use the tree for convergecasting their values, computing the max as the messages move up the tree. The broadcast and convergecast phases do not exceed the bounds for the BFS construction. (k) T F [4 points] Suppose a file server stores a hash of every file in addition to the file contents. When you download a file from the server, you also download the hash and confirm that it matches the file. This system securely verifies that the downloaded file has not been modified by an adversary, provided the hash function has collision resistance. Solution: False. This scheme is not secure because the adversary can simply replace the file with any file and the hash of that file, and you cannot tell the difference. 6.046J/18.410J Final Solutions (l) T F Name [4 points] Suppose Alice, Bob, and Charlie secretly generate a, b and c, respec­ tively, and publish g a mod p, g b mod p, and g c mod p, where p is a prime. Then, Alice, Bob, and Charles can each compute g abc mod p as a shared secret known only to the three of them. Solution: False. For example, Alice only knows a, g b and g c , so she can compute g ab and g ac but not g abc . (m) T F [4 points] The number of memory transfers used by the best cache-oblivious algorithm is always at least the number of memory transfers used by the best external-memory algorithm for the same problem. Solution: True. Make implicit memory transfers explicit, using LRU. (n) T F [4 points] If there is a time-optimal divide-and-conquer algorithm for a problem, then that algorithm is also optimal with respect to memory transfers in the cacheoblivious model. Solution: False. Example: binary search. 5 6.046J/18.410J Final Solutions Name 6 ¨ Problem 2. Uberstructure [10 points] (1 part) Design a data structure that maintains a dynamic set S of n elements subject to the following operations and time bounds: 1. 2. 3. 4. 5. Operation I NSERT(x, S) D ELETE(x, S) S UCCESSOR(x, S) F IND -M IN(S) S EARCH(x, S) Effect Insert x into S. Delete x from S. Find the smallest element in S larger than x. Return the smallest element in S. Return TRUE if element x is in S. Time Bound O(log n) expected amortized O(log n) expected amortized O(log n) worst-case worst-case O(1) expected O(1) Describe how the operations are implemented on your data structure and justify their runtime. Solution: Use a balanced binary search tree and a hash table. Augment the root of the balanced binary search tree with the value of the minimum element. I NSERT: Insert the element in both the balanced binary search tree and hash table. If the element is smaller than the current min, update the root’s stored min value. Insertion into the tree requires O(log n) worst-case time, and insertion into the hash table requires O(1) expected amortization time, for a total of O(log n) expected amortized. (In fact, with high probability, insertion into the hash table requires at most O(log n).) D ELETE: Find the item in the tree and the hash table, and delete it from both. Rebalance the tree as necessary and update the root’s min value if the minimum element has been deleted. Deletion, including rebalancing, costs O(log n), and it takes O(log n) to find the minimum element using the binary search tree. F IND -M IN: Return the min value stored at the root node. This takes O(1) worst-case time. S EARCH: Check whether the element exists in the hash table. This takes O(1) expected time. 6.046J/18.410J Final Solutions Name 7 Problem 3. Meancorp [15 points] (2 parts) You are in charge of the salary database for Meancorp, which stores all employee salaries in a 2-3 tree ordered by salary. Meancorp compiles regular reports to the Department of Fairness about the salary for low-income employees in the firm. You are asked to implement a new database operation AVERAGE(x) which returns the average salary of all employees whose salary is at most x. (a) [10 points] What extra information needs to be stored at each node? Describe how to answer an AVERAGE(x) query in O(lg n) time using this extra information. Solution: Each node x should store x.size — the size of the subtree rooted at x — and x.sum — the sum of all the key values in the subtree rooted at x. For a value x > 0, let Sx be the set of all keys less than or equal to x. Let Ax and Bx be the sum and the size of Sx . We can compute Ax as follows. Let u be the leaf with smallest key larger than x. Finding u from the root only takes O(lg n) time by using S EARCH in a 2-3 tree. Now consider the path from the root of the tree to u. Clearly, Ax is the sum of all leaves that are on the left of this path. Therefore, Ax can be computed by summing up all y.sum’s for every node y that is a left sibling of a node in the path. Since there are only lg n such nodes y’s, computing Ax only takes O(lg n) time. Computing Bx is similar: instead of summing up y.sum, we sum up y.size. There­ fore, it also takes O(lg n) time to compute Bx . Ax can be answered in O(lg n)) time. Therefore, AVERAGE(x) which is B x (b) [5 points] Describe how to modify I NSERT to maintain this information. Briefly justify that the worst-case running time for I NSERT remains O(lg n). Solution: Maintaining x.size is similar to what was covered in recitation and home­ work. Maintaining x.sum is exactly the same: when a node x gets inserted, we simply increase y.sum for every ancestor y of x by the amount x.key. When a node splits, we recompute the x.sum attribute for the split nodes and its parent. Hence, I NSERT still runs in worst-case time O(lg n). 6.046J/18.410J Final Solutions Name 8 Problem 4. Forgetful Forrest [15 points] (3 parts) Prof. Forrest Gump is very forgetful, so he uses automatic calendar reminders for his appointments. For each reminder he receives for an event, he has a 50% chance of actually remembering the event (decided by an independent coin flip). (a) [5 points] Suppose we send Forrest k reminders for each of n events. What is the expected number of appointments Forrest will remember? Give your answer in terms of k and n. Solution: These are all independent events. So linearity of expectation applies. Each given event has been remembered with probability 1 − 2−k . So in expectation n(1 − 2−k ) appointments are remembered. (b) [5 points] Suppose we send Forrest k reminders for a single event. How should we set k with respect to n so that Forrest will remember the event with high probability, i.e., 1 − 1/nα ? Solution: This problem is equivalent to how many times we must flip a coin to get a head with high probability. The probability of k tails in a row is 1/2k . Thus exactly α lg n coin flips suffice. (c) [5 points] Suppose we send Forrest k reminders for each of n events. How should we set k with respect to n so that Forrest will remember all the events with high probability, i.e., 1 − 1/nα ? Solution: We must send at least k = Ω(lg n) reminders, because we needed this many reminders to remember one event with high probability. If we send k = (α + 1) lg n reminders, then each event is remembered with proba­ bility 1 − 1/nα+1 . By a union bound, we know that all events are remembered with probability 1 − 1/nα . So, the number of reminders needed is k = O(lg n). 6.046J/18.410J Final Solutions Name 9 Problem 5. Piano Recital [15 points] (3 parts) Prof. Chopin has a piano recital coming up, and in preparation, he wants to learn as many pieces as possible. There are m possible pieces he could learn. Each piece i takes pi hours to learn. Prof. Chopin has a total of T hours that he can study by himself (before getting bored). In addition, he has n piano teachers. Each teacher j will spend up to tj hours teaching. The teachers are very strict, so they will teach Prof. Chopin only a single piece, and only if no other teacher is teaching him that piece. Thus, to learn piece i, Prof. Chopin can either (1) learn it by himself by spending pi of his T selflearning budget; or (2) he can choose a unique teacher j (not chosen for any other piece), learn together for min{pi , tj } hours, and if any hours remain (pi > tj ), learn the rest using pi − tj hours of his T self-learning budget. (Learning part of a piece is useless.) (a) [6 points] Assume that Prof. Chopin decides to learn exactly k pieces. Prove that he needs to consider only the k lowest pi s and the k highest tj s. Solution: Assume there exists a selection of teachers and pieces for learning k pieces. Let the set of lowest k pieces be Pk . If there is a piece in our selection that is ∈ / Pk , then we must have a piece in Pk not in the final selection. If we swap the one with the higher cost (∈ / Pk ) with the one with lower cost (∈ Pk ), the new selection thus made will still be valid, because if the higher time cost was fulfilled in the previous selection, the lower time cost in the new selection will still be fulfilled. In this way, we can swap pieces until all of them are ∈ Pk . Similarly, we can swap the teachers for those of higher value until they are the ones with the k highest times. 6.046J/18.410J Final Solutions Name (b) [5 points] Assuming part (a), give an efficient greedy algorithm to determine whether Prof. Chopin can learn exactly k pieces. Argue its correctness. Solution: Let us sort all the teachers and pieces in increasing order beforehand. Call the sorted lists P and T . We see that if a solution exists, there is also one in which P1 is paired with Tn−k+1 , P2 is paired with Tn−k+2 and so on. So for each 1 ≤ i ≤ k, the greedy algorithm checks if Pi ≤ Tn−k+i . If it is, then we don’t need to use the shared time for this piece. If it is not, we need to use Tn−k+i − Pi of the shared time. We can add up these values. In the end, if the total shared time we need is > T , we return false. Otherwise, we return true. This takes O(k) time, apart from the initial sorting. (c) [4 points] Using part (b) as a black box, give an efficient algorithm that finds the maximum number of pieces Prof. Chopin can learn. Analyze its running time. Solution: Notice that if kmax is the maximum value of pieces we can learn, we can also learn k pieces for any k ≤ kmax . This suggests that we binary search over the value of k. We try O(log n) values during the binary search, and checking each value takes O(n) time. This takes O(n log n) time. The sorting also took O(n log n) time, so the algo­ rithm takes O(n log n) time overall. 10 6.046J/18.410J Final Solutions Name 11 Problem 6. Be the Computer [14 points] (3 parts) Consider the following flow network and initial flow f . We will perform one iteration of the Edmonds–Karp algorithm. 7:9$ 2" 10:10$ 1:15$ 2:4$ 2:3$ s" 7:7$ 3" 4" 8:9$ 6" 14:30$ 7:10$ 0:15$ 4:6$ 1:4$ 13:15$ 5" 0:15$ t" 10:10$ 7" (a) [5 points] Draw the residual graph Gf of G with respect to f . Solution: 2# 2" 10# 2# 1# s" 13# 2# 2# 1# 15# 14# 7# 3" 2# 5" 7# 6" 7# 3# 1# t" 8# 2# 1# 3# 4" 15# 4# 16# 14# 10# 7" (b) [4 points] List the vertices in the shortest augmenting path, that is, the augmenting path with the fewest possible edges. Solution: s→3→2→5→t or s→3→2→6→t 6.046J/18.410J Final Solutions Name (c) [5 points] Perform the augmentation. What is the value of the resulting flow? Solution: 26. The augmenting flow has value 1. 12 6.046J/18.410J Final Solutions Name 13 Problem 7. Startups are Hard [20 points] (3 parts) For your new startup company, Uber for Algorithms, you are trying to assign projects to employees. You have a set P of n projects and a set E of m employees. Each employee e can only work on one project, and each project p ∈ P has a subset Ep ⊆ E of employees that must be assigned to p to complete p. The decision problem we want to solve is whether we can assign the employees to projects such that we can complete (at least) k projects. (a) [5 points] Give a straightforward algorithm that checks whether any subset of k projects can be completed to solve the decisional problem. Analyze its time com­ plexity in terms of m, n, and k. Solution: For each nk subsets of k projects, check whether any employee is required by more than one project. This can be done simply by going each of the k projects p, marking the employees in Ep as needed, and if any employee is marked twice, then this subset fails. Output “yes” if any subset of k project can be completed, and “no” otherwise. The time complexity is nk ·m because there are nk subsets of size k and we pay O(m) time per subset (because all but one employee will be marked only once). Asymptoti­ cally, this is (n/k)k m. (b) [5 points] Is your algorithm in part (a) fixed-parameter tractable? Briefly explain. Solution: No. An FPT algorithms requires a time complexity of nO(1) f (k). By con­ trast, in our running time, the exponent on n increases with k. 6.046J/18.410J Final Solutions Name (c) [10 points] Show that the problem is NP-hard via a reduction from 3D matching. Recall the 3D matching problem: You are given three sets X, Y , Z, each of size m; a set T ⊆ X × Y × Z of triples; and an integer k. The goal is to determine whether there is a subset S ⊆ T of (at least) k disjoint triples. Solution: Each (x, y, z) ∈ T becomes a project that requires employees E(x,y,z) = {ex , ey , ez }. Thus n = |T |, E = X ∪ Y ∪ Z, and m = |X| + |Y | + |Z|. We set k to be the same in both problems. The size of the matching is equal to the number of projects that can be completed because both problems model disjointness: if k projects can be completed, a subset S of size k can be found, and vice versa. The reduction takes polynomial time. 14 6.046J/18.410J Final Solutions Name 15 Problem 8. Load Balancing [15 points] (2 parts) Suppose you need to complete n jobs, and the time it takes to complete job i is ti . You are given m identical machines M1 , M2 , . . . , Mm to run the jobs on. Each machine can run only one job at a time, and each job must be completely run on a single machine. If you assign a set m Jj ⊆ {1, 2, . . . , n} of jobs to machine Mj , then it will need Tj = i∈Jj ti time. Your goal is to partition the n jobs among the m machines to minimize maxi Ti . (a) [5 points] Describe a greedy approximation algorithm for this problem. of jobs that Mj will run, and Tj to be the total time it Solution: Let Jj to be the set m machine Mj is busy (i.e., Tj = i∈Jj ti ). Initially, Jj = ∅, and Tj = 0 for all j. For i = 1, . . . , n, assign job i to machine Mj such that Tj = min1≤k≤m (Tk ). That is, Jj = Jj ∪ i and Tj = Tj + ti . Output Jj ’s. This runs in O(n lg m) time by keeping a min-heap of the machines based on the current total runtime of each machine. Solution: Alternate solution: Sort jobs in non-increasing order. Without loss of gen­ erality, let the jobs in order be t1 , . . . , tn . Let Jj = {tk:k≡j mod m }. Variations of this algorithm also works, with different sorting orders and assignments. This takes O(n lg n) time to sort the jobs. 6.046J/18.410J Final Solutions Name 16 (b) [10 points] Show that your algorithm from part (a) is a 2-approximation algorithm. Hint: Determine an ideal bound on the optimal solution OPT. Then consider the ma­ chine MT with the longest TT , and the last job i∗ that was added to it. m Solution: A lower bound to the optimal is L = max( m1 1≤i≤n ti , maxi (ti )) since the best you can do is to evenly divide the fractional jobs, and it has to run for at least as long as the longest job. Now let MT be the machine that runs for the longest, and let i∗ be the last job that was assigned to MT using the greedy algorithm. Let Tj∗ be the total run time of all jobs of Mj immediately before assigning i∗ ; TT∗ = minj Tj∗ . Then we have m · TT∗ ≤ Tj∗ = 1≤j≤m ti ≤ 1≤i≤i∗ ti ≤ m · L, 1≤i≤n which implies that TT∗ ≤ L. Putting it together, we have TT = TT∗ + ti∗ ≤ L + ti∗ ≤ 2L ≤ 2OP T . Therefore, this is a 2-approximation algorithm. Solution: Proof for alternate solution: Let L be the lower defined above. Consider the longest job tn . Let k ≡ n mod m, and let Sk = Tk − tn . It must be that Sk ≤ Tj for all j: for j > k, we only added elements at least as large as every element of Sk . For j < k, there are a = i m l jobs, and the last a − 1 jobs in Jj are greater the first a − 1 n jobs of Jk due to the jobs being sorted, which shows that Sk ≤ Tj . Then n Tj ≥ tn + mSk . ti = tn + Sk + i=1 j=k # m Therefore, mSk ≤ ni=1 ti , which implies Sk ≤ L. Since tn ≤ L also, we get that tn + Sk ≤ 2L ≤ 2OP T . 6.046J/18.410J Final Solutions Name 17 Problem 9. Distributed Coloring [20 points] (3 parts) Consider an undirected graph G = (V, E) in which every vertex has degree at most Δ. Define a new graph G' = (V ' , E ' ), the Cartesian product of G with a clique of size Δ + 1. Specifically, V ' is the set of pairs (v, i) for all vertices v ∈ V and integers i with 0 ≤ i ≤ Δ, and E ' consists of two types of edges: 1. For each edge {u, v} ∈ E, there is an edge between (u, i) and (v, i) in E ' , for all 0 ≤ i ≤ Δ. (Thus, each index i forms a copy of G.) 2. For each vertex v ∈ V , there is an edge between (v, i) and (v, j) in E ' , for all i = j with 0 ≤ i, j ≤ Δ. (Thus each v forms a (Δ + 1)-clique.) Here is an example of this transformation with Δ = 3: Figure 1: Graph G. Figure 2: The Cartesian product G' of G and a clique of size 4. (a) [8 points] Let S be any maximal independent set of G' (i.e., adding any other vertex to S would violate independence). Prove that, for each vertex v ∈ V , S contains exactly one of the Δ + 1 vertices in V ' of the form (v, i). Hint: Use the Pigeonhole Principle. Solution: It cannot contain more than one, since all of these are connected in G' and that would violate independence. Now suppose for contradiction that, for some particular u, S contains no vertices of the form (u, i). Then by maximality, every vertex of the form (u, i) must have some G' -neighbor in S. Since that neighbor is not of the form (u, ∗), it must be of the form (v, i), for some v with (u, v) ∈ E. Thus, each of the Δ + 1 vertices of the form (u, i) has some neighbor of the form (v, i) in S, where (u, v) ∈ E. Since u has at most Δ neighbors in G, by the Pigeonhole Principle, there must be two different values of i, say i1 and i2 , for which there is a single v such that (u, ii ) is a G' -neighbor of (v, i1 ), (u, i2 ) is a G' -neighbor of (v, i2 ), and both (v, i1 ) and (v, i2 ) are in S. That is a contradiction because S can contain at most one vertex of the form (v, ∗). 6.046J/18.410J Final Solutions Name (b) [8 points] Now consider a synchronous network of processes based on the graph G, where every vertex knows an upper bound Δ on the degree. Give a distributed algo­ rithm to find a vertex (Δ + 1)-coloring of G, i.e., a mapping from vertices in V to colors in {0, 1, . . . , Δ} such that adjacent vertices have distinct colors. The process associated with each vertex should output its color. Argue correctness. Hint: Combine part (a) with Luby’s algorithm. Solution: The “colors” will be chosen from {0, 1, . . . , Δ}. The nodes of G simulate an MIS algorithm for G' . Specifically, the node associated with vertex u of G simulates the Δ + 1 nodes associated with vertices of the form (u, i) of G' . The algorithm produces an MIS S for G' , where each node of G learns which of its simulated nodes correspond to vertices in S. By Part (a), for each vertex u of G, there is a unique color i such that (u, i) ∈ S; the node associated with u chooses this color i. Obviously, this strategy uses at most Δ + 1 colors. To see that no two neighbors in G are colored with the same color, suppose for contradiction that neighbors u and v are colored with the same color, say i. That means that both (u, i) and (v, i) are in S. But (u, i) and (v, i) are neighbors in G' , contradicting the independence property for S. An alternative solution that many students wrote involved executing Δ + 1 instances of Luby’s MIS directly on G, in succession. In each instance i, the winners are colored with color i. Then we remove just the winners before executing the next instance. This works, but leaves out some details w.r.t. synchronizing the starts of the successive instances. Also, its performance is quite a bit worse than the recommended solution above. (c) [4 points] Analyze the expected time and communication costs for solving the color­ ing problem in this way, including the cost of Luby’s algorithm. Solution: The costs are just those of solving MIS on G' ; the final decisions are local and don’t require any extra rounds. Time (number of rounds): The expected time to solve MIS on G' is O(lg (n · Δ)), because the number of nodes in G' is n · (Δ + 1). The O(lg (n · Δ)) bound can be simplified to O(lg n). Communication (number of messages): The expected number of messages is O(E lg n), corresponding to O(lg n) rounds and messages on all edges (in both directions) at each round. 18