Introduction to Algorithms December 14, 2010Massachusetts Institute of Technology 6.006 Fall 2010Professors Konstantinos Daskalakis and Patrick Jaillet Final ExamFinal Exam• Do not open this quiz booklet until directed to do so. Read all the instructions on this page.• When the quiz begins, write your name on every page of this quiz booklet.• You have 180 minutes to earn 180 points. Do not spend too much time on any one problem.Read them all first, and attack them in the order that allows you to make the most progress.• This exam is closed book. You may use three 81200× 1100or A4 crib sheets (both sides). Nocalculators or programmable devices are permitted. No cell phones or other communicationsdevices are permitted.• Write your solutions in the space provided. If you need more space, write on the back of thesheet containing the problem. Pages may be separated for grading.• Don’t waste time and paper rederiving facts that we have studied. It is sufficient to citeknown results.• When writing an algorithm, a clear description will suffice. Pseudo-code isn’t required.• When asked for an algorithm, your algorithm should have the time complexity specified inthe problem with a correct analysis. If you cannot find such an algorithm, you will generallyreceive partial credit for a slower algorithm if you analyze your algorithm correctly.• 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.Problem Parts Points Grade Grader1 2 22 1 303 2 304 2 285 3 306 3 307 2 30Total 180Name:FridayRecitation:Aleksander11 AMArnab12 PMAlina3 PMMatthew4 PM6.006 Final Exam Name 2Problem 1. What is Your Name? [2 points] (2 parts)(a) [1 point] Flip back to the cover page. Write your name there.(b) [1 point] Flip back to the cover page. Circle your recitation section.6.006 Final Exam Name 3Problem 2. Storing Partial Maxima [30 points] (1 part)6.006 student, Mike Velli, wants to build a website where the user can input a time interval inhistory, and the website will return the most exciting sports event that occurred during this interval.Formally, suppose that Mike has a chronologically sorted list of n sports events with associatedinteger “excitement factors” e1, . . . , en. You can assume for simplicity that n is a power of 2. Auser’s query will consist of a pair (i, j) with 1 ≤ i < j ≤ n, and the site is supposed to returnmax(ei, ei+1, . . . , ej).Mike wishes to minimize the amount of computation per query, since there will be a lot of trafficto the website. If he precomputes and stores max(ei, . . . , ej) for every possible input (i, j), he canrespond to user queries quickly, but he needs storage Ω(n2) which is too much.In order to reduce storage requirements, Mike is willing to allow a small amount of computationper query. He wants to store a cleverer selection of precomputed values than just max(ei, . . . , ej)for every (i, j), so that for any user query, the server can retrieve two precomputed values and takethe maximum of the two to return the final answer. Show that now only O(n log n) values need tobe precomputed.6.006 Final Exam Name 4Problem 3. Longest Simple Cycle [30 points] (2 parts)Given an unweighted, directed graph G = (V, E), a path hv1, v2, ..., vni is a set of vertices suchthat for all 0 < i < n, there is an edge from vito vi+1. A cycle is a path such that there is also anedge from vnto v1. A simple path is a path with no repeated vertices and, similarly, a simple cycleis a cycle with no repeated vertices. In this question we consider two problems:• LONGESTSIMPLEPATH: Given a graph G = (V, E) and two vertices u, v ∈ V , find a simplepath of maximum length from u to v or output NONE if no path exists.• LONGESTSIMPLECYCLE: Given a graph G = (V, E), find a simple cycle of maximumlength in G.(a) [20 points] Reduce the problem of finding the longest simple path to the problem offinding the longest simple cycle. Prove the correctness of your reduction and showthat it runs in polynomial time in |V | and |E|.(b) [10 points] As we discussed in class, finding a longest simple path is NP-Hard. There-fore, there is no known algorithm that, on input u, v, and G returns a longest simplepath from u to v in polynomial time. Using this fact (which you do not need to prove)and Part (a), show that there is no known polynomial time algorithm that can find alongest simple cycle in a graph.Note: If you were unable to solve Part (a), you may assume an algorithm SIM-PLEPATHFROMCYCLE for finding a longest simple path from u to v that runs in timepolynomial in L, |V |, and |E| where L is the running time of a black-box algorithmfor solving LONGESTSIMPLECYCLE.6.006 Final Exam Name 5Problem 4. Closest pair [28 points] (2 parts)We are interested in finding the closest pair of points in the plane, closest in the sense of therectilinear distance (also called the Manhattan or L1distance). The rectilinear distance betweentwo points p1and p2on the plane is defined as d(p1, p2) = |x1−x2|+|y1−y2|, where the x’s and y’sare the first and second coordinates, respectively. In the first part we consider a one-dimensionalversion of the problem as a warm-up. In both cases, coordinates of the points are real numberswith k significant digits beyond the decimal point, k constant.(a) [8 points] Warm up - Provide an efficient way to find a closest pair among n points inthe interval [0, 1] on the line. Full credit will be given to the most efficient algorithmwith a correct analysis.(b) [20 points] Case of the plane - A divide and conquer approach for n points in thesquare [0, 1] × [0, 1]. Here is a possible strategy. Divide the set of points into two setsof about half size: those on the right of the x-coordinate median, and those on the left.Recursively, find the closest pair of points on the right, and the closest pair of pointson the left and let δrand δlbe the corresponding distances. The overall closest pair iseither the minimum of these two options, or corresponds to a pair where one point ison the right of the median and the other is on the left. Given δrand δl, there should bean efficient way to find the latter. Explain how; then write the full recurrence for therunning time of this approach; and conclude with its overall running time.6.006 Final Exam Name 6Problem 5. APSP Algorithm for Sparse Graphs [30 points] (3 parts)Let G = (V, E) be a weighted, directed graph
View Full Document
Unlocking...