May 19 2010 6 006 Spring 2010 Final Examination Introduction to Algorithms Massachusetts Institute of Technology Professors Piotr Indyk and David Karger Final Examination 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 through first and attack them in the order that allows you to make the most progress 00 This quiz 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 Do not waste time and paper rederiving facts that we have studied It is sufficient to cite known results When writing an algorithm a clear description in English will suffice Pseudo code is not 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 Be neat Good luck Problem Parts Points 1 7 21 2 9 54 3 3 15 4 3 20 5 4 25 6 4 25 7 3 20 Total Grade Grader 180 Name Friday Recitation Zuzana 10 AM Debmalya 11 AM Ning 12 PM Matthew 1 PM Alina 2 PM Alex 3 PM 6 006 Final Examination Name 2 Problem 1 True or False 21 points 7 parts For each of the following questions circle either T True or F False There is no penalty for incorrect answers You are not required to give any justification for your answer a T F 3 points Every vertex reachable from a vertex v in an undirected graph G is either a descendant or an ancestor of v in any DFS tree of G b T F 3 points In the DAG representation of a dynamic program an edge between two sub problems indicates that they are identical c T F 3 points Assuming simple uniform hashing the collision probability of a new key being inserted in a hash table using open addressing is at least as much as in a hash table using chaining Assume that both hash tables are of the same size and contain the same set of keys d T F 3 points If problem A is polynomial time reducible to problem B and A is in P then B is in P as well e T F 3 points Heapsort is a stable sorting algorithm f T F 3 points The 2 SAT problem is a constrained version of the SAT problem where every clause may contain at most two literals 2 SAT is NP hard since it is a special case of SAT g T F 3 points We can design an algorithm that sorts any 5 numbers using 6 comparisons 6 006 Final Examination Name 3 Problem 2 Short Answers 54 points 9 parts For each of the following questions you are expected to give a short answer that fits in the space provided for each question a 7 points Suppose that an algorithm runs on a tree containing n nodes What is the time complexity of the algorithm if the time spent per node in the tree is proportional to 3 points the number of children of the node Assume that the algorithm spends O 1 time per leaf 4 points the number of grandchildren of the node Assume that the algorithm spends O 1 time for every node that does not have a grandchild b 5 points Solve the following recurrence T n T n O 1 if n 2 T n O 1 otherwise 6 006 Final Examination Name 4 c 8 points For each of the following schemes in an expanding hash table explain why it does or does not result in O 1 amortized cost per insertion operation You may assume that no key is deleted 2 points Increase the size by 1 on every insertion 2 points Increase the size by 50 every time the load factor is at least 0 75 2 points Square the size every time the load factor is at least 0 75 2 points Grow the size by 1 every time the load factor is at least 0 30 d 5 points Assuming simple uniform hashing show that the probability of no collision when n keys are inserted in a hash table of size n2 is at least 1 2 Hint You might want to use the union bound which states that for a set of k events E1 E2 Ek k X k Prob i 1 Ei Prob Ei i 1 6 006 Final Examination Name 5 e 6 points Given a weighted undirected graph the k Traveling Salesman Problem kTSP asks whether the weight of the shortest cycle containing all vertices is at most k Show that k TSP is NP hard by a reduction from the Hamiltonian cycle problem Hint Consider the k TSP problem on a graph with only two types of edges edges with weight 1 or f 6 points Let G be the following weighted undirected graph qD qqq q q q qqq qqq 8 NNN NNN 2 NNN NNN N E qqq 2 qqq q qqq qqq 4 NNN NNN NNN 7 NNN N 5 B qqq q q qq qqq q q q 5 MMM MMM MMM 3 MMM M 9 A C F Suppose that we were to run Dijkstra s algorithm starting from vertex A In what order are the vertices extracted from the priority queue 6 006 Final Examination Name g 8 points Suppose that you have a processor that enables you to perform a 3 way comparison in O 1 time In other words given three distinct numbers a b c the comparator outputs a b c or a c b or b a c or b c a or c a b or c b a depending on the relative magnitudes of the numbers Using such a comparator is it possible to sort any 6 distinct numbers using three 3 way comparisons Justify h 4 points In modern software development a useful utility called make is usually employed to manage the compilation order of files The problem is you are given n files that need to be compiled Some of the files can only compile when some other files have been compiled Your job is to find an ordering to compile the n files Can you solve this problem in polynomial in n time by some algorithm you learned in this course you only need to spell …
View Full Document
Unlocking...