Introduction to Algorithms May 19, 2010Massachusetts Institute of Technology 6.006 Spring 2010Professors Piotr Indyk and David Karger Final ExaminationFinal 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 allthrough first, and attack them in the order that allows you to make the most progress.• This quiz is closed book. You may use three 81200× 1100or A4 crib sheets (both sides). No calculators orprogrammable 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 containingthe 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 witha correct analysis. If you cannot find such an algorithm, you will generally receive partial credit for a sloweralgorithm 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 Grade Grader1 7 212 9 543 3 154 3 205 4 256 4 257 3 20Total 180Name:FridayRecitation:Zuzana10 AMDebmalya11 AMNing12 PMMatthew1 PMAlina2 PMAlex3 PM6.006 Final Examination Name 2Problem 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 forincorrect 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 iseither 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 betweentwo sub-problems indicates that they are identical.(c) T F [3 points] Assuming simple uniform hashing, the collision probability of a newkey being inserted in a hash table using open addressing is at least as much as ina hash table using chaining. (Assume that both hash tables are of the same sizeand contain the same set of keys.)(d) T F [3 points] If problem A is polynomial-time reducible to problem B and A is inP, 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 problemwhere 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 compar-isons.6.006 Final Examination Name 3Problem 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 spaceprovided for each question.(a) [7 points] Suppose that an algorithm runs on a tree containing n nodes. What is thetime complexity of the algorithm if the time spent per node in the tree is proportionalto:• [3 points] the number of children of the node? (Assume that the algorithm spendsO(1) time per leaf.)• [4 points] the number of grandchildren of the node? (Assume that the algorithmspends 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 > 2T (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 whyit does or does not result in O(1) amortized cost per insertion operation. You mayassume 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 collisionwhen n keys are inserted in a hash table of size n2is at least 1/2.Hint: You might want to use the union bound which states that for a set of k eventsE1, E2, . . . , Ek,Prob[∪ki=1Ei] ≤kXi=1Prob[Ei].6.006 Final Examination Name 5(e) [6 points] Given a weighted undirected graph, the k-Traveling Salesman Problem (k-TSP) asks whether the weight of the shortest cycle containing all vertices, is at mostk. 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—edgeswith weight 1 or ∞.)(f) [6 points] Let G be the following weighted undirected graph:D8B55qqqqqqqqqqqqq2NNNNNNNNNNNNNA9qqqqqqqqqqqqq3MMMMMMMMMMMMME4C2qqqqqqqqqqqqq7NNNNNNNNNNNNNFSuppose that we were to run Dijkstra’s algorithm starting from vertex A. In what orderare the vertices extracted from the priority queue?6.006 Final Examination Name 6(g) [8 points] Suppose that you have a processor that enables you to perform a 3-waycomparison in O(1) time. In other words, given three distinct numbers a, b, c, thecomparator outputs a < b < c or a < c < b or b < a < c or b < c < a orc < a < b or c < b < a depending on the relative magnitudes of the numbers. Usingsuch a comparator, is it possible to sort any 6 distinct numbers using three 3-waycomparisons? Justify.(h) [4 points] In modern software development, a useful utility called make is usuallyemployed to manage the compilation order of files. The problem is: you are given nfiles that need to be compiled. Some of the files can only compile when some otherfiles have been compiled. Your job is to find an ordering to compile the n files. Canyou solve this problem in polynomial (in n) time by some algorithm you learned inthis course (you only need to spell out the name of the algorithm)? If so, what is therunning time of your algorithm?(i) [5 points] Suppose you want to estimate the value of 1000/7. Show that if the startingvalue is x0= 109in Newton’s method for division, then you will never get to a valuethat is accurate to 6 decimal places.6.006 Final Examination Name 7Problem 3. Finding Bridges [15 points] (3
View Full Document
Unlocking...