6.046J Spring 2011, Practice Final Exam, Solutions

May 12, 2011 6.046J/18.410J Practice Final Exam Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Dana Moshkovitz and Bruce Tidor Practice Final Exam • Do not open this quiz booklet until you are directed to do so. Read all the instructions first. • The quiz contains 6 problems, several with multiple parts. You have 180 minutes to earn 120 points. • This quiz booklet contains 15 pages, including this one, and a sheet of scratch paper which can be detached. ′′ • This quiz is closed book. You may use two double sided Letter (8 21 ×11′′ ) or A4 crib sheets. No calculators or programmable devices are permitted. Cell phones must be put away. • Write your solutions in the space provided. If you run out of space, continue your answer on the back of the same sheet and make a notation on the front of the sheet. • Do not waste time deriving facts that we have studied. It is sufficient to cite known results. • 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 correctness of your answer, but also on the clarity with which you express it. Please be neat. • Good luck! Problem Title 0 Name 1 15 1 True or False 44 11 2 P, NP & Friends 10 1 3 Taming M AX -C UT 10 3 4 Spy Games 10 2 5 Lots of Spanning trees 25 5 6 Traveling with the salesman 20 3 Total Name: Points Parts Grade 120 Initials 6.046J/18.410J Practice Final Exam 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. [44 points] (11 parts) Circle T or F for each of the following statements to indicate whether the statement is true or false, respectively, and briefly explain why. Your justification is worth more points than your true-or-false designation. (a) T F [4 points] If problem A can be reduced to 3SAT via a deterministic polynomialtime reduction, and A ∈ NP, then A is NP-complete. Solution: False. We need to reduce in the other direction (reduce an NP-hard problem to A). (b) T F [4 points] Let G = (V, E) be a flow network, i.e., a weighted directed graph with a distinguished source vertex s, a sink vertex t, and non-negative capacity c(u, v) for every edge (u, v) in E. Suppose you find an s-t cut C which has edges e1 , e2 , . . . , ek and a capacity f . Suppose the value of the maximum s-t flow in G is f . Now let H be the flow network obtained by adding 1 to the capacity of each edge in C. Then the value of the maximum s-t flow in H is f + k. Solution: False. There could be multiple min-cuts. Consider the graph s-v-t where the edges have capacity 1; either edge in itself is a min-cut, but adding capacity to that edge alone does not increase the max flow. 6.046J/18.410J Practice Final Exam Name (c) T F [4 points] Let A and B be optimization problems where it is known that A reduces to B in polynomial time. Additionally, it is known that there exists a polynomial-time 2-approximation for B. Then there must exist a polynomialtime 2-approximation for A. Solution: False. approximation factor is not (necessarily) carried over in polytime reduction. See e.g. set cover vs. vertex cover. (d) T F [4 points] There exists a polynomial-time 2-approximation algorithm for the general Traveling Salesman Problem. Solution: False, assuming P 6= NP. There is an approximation algorithm in the special case where the graph obeys the triangle inequality, but we don’t know of one in general. 3 6.046J/18.410J Practice Final Exam Name (e) T F [4 points] If we use a max-queue instead of a min-queue in Kruskal’s MST algorithm, it will return the spanning tree of maximum total cost (instead of returning the spanning tree of minimum total cost). (Assume the input is a weighted connected undirected graph.) Solution: True. The proof is essentially the same as for the usual Kruskal’s algorithm. Alternatively, this is equivalent to negating all the edge weights and running Kruskal’s algorithm. (f) T F [4 points] A randomized algorithm for a decision problem with one-sided-error and correctness probability 1/3 (that is, if the answer is YES, it will always output YES, while if the answer is NO, it will output NO with probability 1/3) can always be amplified to a correctness probability of 99%. Solution: True. Since the error is one-sided, it in fact suffices for the correctness probability to be any constant > 0. We can then repeat it, say, k times, and output NO if we ever see a NO, and YES otherwise. Then, if the correct answer is YES, all k repetitions of our algorithm will output YES, so our final answer is also YES, and if the correct answer is NO, each of our k repetitions has a 1/3 chance of returning NO, in which case our final answer is, correctly, NO, with probability 1 − (2/3)k , so k = log3/2 100 repetitions suffice. 4 6.046J/18.410J Practice Final Exam Name (g) T F [4 points] Suppose that a randomized algorithm A has expected running time Θ(n2 ) on any input of size n. Then it is possible for some execution of A to take Ω(3n ) time. Solution: True. Imagine a scenario where the runtime of A is Θ(3n ) with probability n2 3−n , and Θ(n2 ) otherwise. It is apparent that the expected run time of A is Θ(n2 ). But, with non-zero probability some execution may take Ω(3n ) time . (h) T F [4 points] Building a heap on n elements takes Θ(n lg n) time. Solution: False. It can be done in O(n) time. 5 6.046J/18.410J Practice Final Exam (i) T F Name [4 points] We can evaluate a polynomial of degree-bound n at any set of n points in O(n lg n) time. Solution: False. Evaluating a polynomial of degree-bound n at any (arbitrary) set of n points takes O(n lg2 n) time. For details, one may refer to problem 2 of pset 8. (j) T F [4 points] Suppose that you have two deterministic online algorithms, A1 and A2 , with a competitive ratios c1 and c2 respectively. Consider the randomized algorithm A∗ that flips a fair coin once at the beginning; if the coin comes up heads, it runs A1 from then on; if the coin comes up tails, it runs A2 from then on. Then the expected competitive ratio of A∗ is at least min{c1 , c2 }. Solution: False. Suppose the problem is to guess which of two cups holds the bean. Algorithm A1 checks left cup then right cup and has competitive ratio c1 = 2. Algorithm A2 checks right cup then left cup and has competitive ratio c2 = 2. The randomized algorithm has competitive ratio c = 0.5 · 2 + 0.5 · 1 = 1.5 < min{c1 , c2 } 6 6.046J/18.410J Practice Final Exam Name 7 Problem 2. Taming Max-Cut [10 points] A C UT, in a graph G = (V, E), is a partition of V into two non-intersecting sets A, B. An edge is said to be in the cut if one of its end points is in A and the other is in B. In the M AX -C UT problem, the objective is to maximize the number of edges in the cut. We intend to design an approximation scheme for M AX -C UT. Consider the following scheme. Every vertex v ∈ V is assigned to A, B uniformly at random. (a) What is the probability that e ∈ E is in the cut? Solution: With probability 1/2, one vertex of e is assigned to a set different from the other. Thus, the probability that e is in the cut is 1/2. (b) What is the expected number of edges in the cut? Solution: Use an indicator variable for every edge with probability of success(being in the cut) being 1/2. Since, the variables are identical and independent, each experiment is a Bernouli experiement. The expected number of successes among the |E| Bernouli trails is |E|/2. Thus, the expected number of edges in the cut is |E|/2. 6.046J/18.410J Practice Final Exam Name 8 (c) Conclude that the randomized scheme presented above is a 2-approximation to the M AX -C UT. Solution: The maximum number of edges in the cut is |E|. The randomized scheme has no more than 2 times worse than the optimum in expectation. Problem 3. Lots of Spanning Trees. (5 parts) [25 points] Let G = (V, E) be a connected undirected graph with edge-weight function w : E → . Let wmin and wmax denote the minimum and maximum weights, respectively, of the edges in the graph. Do not assume that the edge weights in G are distinct or nonnegative. The following statements may or may not be correct. In each case, either prove the statement is correct or give a counterexample if it is incorrect. R (a) If the graph G has more than |V | − 1 edges and there is a unique edge having the largest weight wmax , then this edge cannot be part of any minimum spanning tree. Solution: False. This heavy edge could be the only edge connecting some vertex to a graph and thus must be included in the MST. 6.046J/18.410J Practice Final Exam Name (b) Any edge e with weight wmin , must be part of some MST. Solution: True. In some ordering of the edges by increasing weight, e will be the first, thus included in the tree constructed by the Kruskal’s algorithm. Any tree constructed by the Kruskal’s algorithm is an MST. (c) If G has a cycle and there is unique edge e which has the minimum weight on this cycle, then e must be part of every MST. Solution: False. Consider the graph of a tetrahedron where the three edges of the base triangle have weights 2, 3, 4 and the three edges connecting the peak to the base all have weight 1. Then the MST is composed of those latter three edges and does not include the edge with weight 2 in the bottom cycle. 9 6.046J/18.410J Practice Final Exam Name (d) If the edge e is not part of any MST of G, then it must be the maximum weight edge on some cycle in G. Solution: True. Take any MST T . Since e is not part of it, e must complete some cycle in T . e must be the heaviest edge on that cycle. Otherwise a smaller weight tree could be constructed by swapping the heavier edge on the cycle with e and thus T cannot be MST. (e) Suppose the edge weights are nonnegative. Then the shortest path between two vertices must be part of some MST. Solution: False. Consider a simple triangle with sides 1, 1, 1.5. The MST is composed of the two lighter edges while the longer edge is the shortest path between two vertices. 10 6.046J/18.410J Practice Final Exam Name 11 Problem 4. Traveling with the salesman. [20 points] In the traveling-salesman problem, a salesman must visit n cities. Modeling the problem as a complete graph on n vertices, we can say that the salesman wishes to make a tour or a hamiltonian cycle, visiting each city exactly only once and finishing at the city he starts from. The salesman incurs a nonnegative integer cost c(i, j) to travel from city i to city j, and the salesman wishes to make a tour whose total cost is minimum, where the total cost is the sum of the individual costs along the edges of the tour. (a) Formulate the traveling salesman problem as a language. TSP = Solution:   A complete graph of n vertices with non-negative edge TSP = < n, c, k > weights c has a hamiltonian cycle of cost at most k. (b) Prove that TSP ∈ NP. Solution: An instance < n, c, k > can be verified to be in TSP given a tour (a permutation of indices) as the certificate. The tour can be easily checked in poly-time to traverse every node exactly once and have a satisfying total cost. A hamiltonian cycle in a graph is a cycle that visits every vertex exactly once. Define the language H AM -C YCLE = {< G >: there is a hamiltonian cycle in G}. (c) Assuming that H AM -C YCLE is complete for the class NP, prove that TSP is NPComplete. Solution: To prove that TSP is NP-Hard, we show the reduction H AM -C YCLE ≤p TSP. Given a graph G = (V, E) we define edge costs (in the complete graph) c(u, v) = 0 if (u, v) ∈ E and c(u, v) = 1 otherwise. If G has a hamiltonian cycle, then that cycle is also a tour of cost 0 in the complete graph with costs c, so < n, c, 0 >∈ TSP. For the converse, if there is a tour in the complete graph with cost 0, then it must traverse edges that are present in G, so this tour is also a hamiltonian cycle in G. TSP is NP-Complete because it is both in NP and NP-Hard.