December 14 2010 6 006 Fall 2010 Final Exam Introduction to Algorithms Massachusetts Institute of Technology Professors Konstantinos Daskalakis and Patrick Jaillet Final 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 00 This exam is closed book You may use three 8 21 1100 or A4 crib sheets both sides No calculators or programmable devices are permitted No cell phones or other communications devices are permitted Write your solutions in the space provided If you need more space write on the back of the sheet 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 cite known 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 in the problem with a correct analysis If you cannot find such an algorithm you will generally receive 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 correctness of your answer but also on the clarity with which you express it Problem Parts Points Grade 1 2 2 2 1 30 3 2 30 4 2 28 5 3 30 6 3 30 7 2 30 Total Grader 180 Name Friday Recitation Aleksander 11 AM Arnab 12 PM Alina 3 PM Matthew 4 PM 6 006 Final Exam Name Problem 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 2 6 006 Final Exam Name 3 Problem 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 in history 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 associated integer excitement factors e1 en You can assume for simplicity that n is a power of 2 A user s query will consist of a pair i j with 1 i j n and the site is supposed to return max ei ei 1 ej Mike wishes to minimize the amount of computation per query since there will be a lot of traffic to the website If he precomputes and stores max ei ej for every possible input i j he can respond 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 computation per 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 take the maximum of the two to return the final answer Show that now only O n log n values need to be precomputed 6 006 Final Exam Name 4 Problem 3 Longest Simple Cycle 30 points 2 parts Given an unweighted directed graph G V E a path hv1 v2 vn i is a set of vertices such that for all 0 i n there is an edge from vi to vi 1 A cycle is a path such that there is also an edge from vn to v1 A simple path is a path with no repeated vertices and similarly a simple cycle is a cycle with no repeated vertices In this question we consider two problems L ONGEST S IMPLE PATH Given a graph G V E and two vertices u v V find a simple path of maximum length from u to v or output NONE if no path exists L ONGEST S IMPLE C YCLE Given a graph G V E find a simple cycle of maximum length in G a 20 points Reduce the problem of finding the longest simple path to the problem of finding the longest simple cycle Prove the correctness of your reduction and show that 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 Therefore there is no known algorithm that on input u v and G returns a longest simple path 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 a longest simple cycle in a graph Note If you were unable to solve Part a you may assume an algorithm S IM PLE PATH F ROM C YCLE for finding a longest simple path from u to v that runs in time polynomial in L V and E where L is the running time of a black box algorithm for solving L ONGEST S IMPLE C YCLE 6 006 Final Exam Name 5 Problem 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 the rectilinear distance also called the Manhattan or L1 distance The rectilinear distance between two points p1 and p2 on the plane is defined as d p1 p2 x1 x2 y1 y2 where the x s and y s are the first and second coordinates respectively In the first part we consider a one dimensional version of the problem as a warm up In both cases coordinates of the points are real numbers with 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 in the interval 0 1 on the line Full credit will be given to the most efficient algorithm with a correct analysis b 20 points Case of the plane A divide and conquer approach for n points in the square 0 1 0 1 Here is a possible strategy Divide the set of points into two sets of 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 points on the left and let r and l be the corresponding distances The overall closest pair is either the minimum of these two options or corresponds to a pair where one point is on the right of the median and the other is on the left Given r and l there should be an efficient way to find the latter Explain how then write the full recurrence for the running …
View Full Document
Unlocking...