Introduction to Algorithms May 21, 2008Massachusetts Institute of Technology 6.006 Spring 2008Professors Srini Devadas and Erik Demaine Final ExamFinal Exam• Do not open this exam booklet until you are directed to do so. Read all the instructions onthis page.• When the exam begins, write your name on every page of this exam booklet.• This exam contains 12 problems, some with multiple parts. You have 180 minutes to earn180 points.• This exam booklet contains 24 pages, including this one. Two extra sheets of scratch paperare attached. Please detach them before turning in your exam at the end of the exam period.• This exam is closed book. You may use three 81200× 1100or A4 crib sheets (both sides). Nocalculators or programmable devices are permitted.• Write your solutions in the space provided. If you need more space, write on the back of thesheet containing the problem. Do not put part of the answer to one problem on the back ofthe sheet for another problem, since the pages may be separated for grading.• Do not waste time and paper rederiving facts that we have studied. It is sufficient to citeknown results.• Do not spend too much time on any one problem. Read them all through first, and attackthem in the order that allows you to make the most progress.• 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. Be neat.• Good luck!Problem Parts Points Grade Grader Problem Parts Points Grade Grader1 1 10 7 2 102 10 40 8 2 103 1 10 9 1 104 2 10 10 3 155 1 10 11 4 206 2 15 12 4 20Total 180Name:Circle your recitation time:Hueihan Jhuang: (10AM) (11AM) Victor Costan (2PM) (3PM)6.006 Final Exam Name 2Problem 1. Asymptotics [10 points]For each pair of functions f (n) and g(n) in the table below, write O, Ω, or Θ in the appropriatespace, depending on whether f(n) = O(g(n)), f(n) = Ω(g(n)), or f(n) = Θ(g(n)). If thereis more than one relation between f(n) and g(n), write only the strongest one. The first line is ademo solution.We use lg to denote the base-2 logarithm.n n lg n n2n lg2n Ω Ω O2lg2nlg(n!)nlg 36.006 Final Exam Name 3Problem 2. True or False [40 points] (10 parts)Decide whether these statements are True or False. You must briefly justify all your answers toreceive full credit.(a) An algorithm whose running time satisfies the recurrence P (n) = 1024 P (n/2) + O(n100)is asymptotically faster than an algorithm whose running time satisfies the recurrenceE(n) = 2 E(n − 1024) + O(1).True FalseExplain:(b) An algorithm whose running time satisfies the recurrence A(n) = 4 A(n/2) + O(1)is asymptotically faster than an algorithm whose running time satisfies the recurrenceB(n) = 2 B(n/4) + O(1).True FalseExplain:6.006 Final Exam Name 4(c) Radix sort works in linear time only if the elements to sort are integers in the range{0, 1, . . . , c n} for some c = O(1).True FalseExplain:(d) Given an undirected graph, it can be tested to determine whether or not it is a tree inO(V + E) time. A tree is a connected graph without any cycles.True FalseExplain:6.006 Final Exam Name 5(e) The Bellman-Ford algorithm applies to instances of the single-source shortest pathproblem which do not have a negative-weight directed cycle, but it does not detect theexistence of a negative-weight directed cycle if there is one.True FalseExplain:(f) The topological sort of an arbitrary directed acyclic graph G = (V, E) can be com-puted in linear time.True FalseExplain:6.006 Final Exam Name 6(g) We know of an algorithm to detect negative-weight cycles in an arbitrary directedgraph in O(V + E) time.True FalseExplain:(h) We know of an algorithm for the single source shortest path problem on an arbitrarygraph with no negative-weights that works in O(V + E) time.True FalseExplain:6.006 Final Exam Name 7(i) To delete the ithnode in a min heap, you can exchange the last node with the ithnode,then do the min-heapify on the ithnode, and then shrink the heap size to be one lessthe original size.True FalseExplain:(j) Generalizing Karatsuba’s divide and conquer algorithm, by breaking each multipli-cand into 3 parts and doing 5 multiplications improves the asymptotic running time.True FalseExplain:6.006 Final Exam Name 8Problem 3. Set Union [10 points]Give an efficient algorithm to compute the union A∪B of two sets A and B of total size |A|+|B| =n. Assume that sets are represented by arrays (Python lists) that store distinct elements in anarbitrary order. In computing the union, the algorithm must remove any duplicate elements thatappear in both A and B.For full credit, your algorithm should run in O(n) time. For partial credit, give an O(n lg n)-timealgorithm.6.006 Final Exam Name 9Problem 4. Balanced Trees [10 points]In the definition of an AVL tree we required that the height of each left subtree be within one ofthe height of the corresponding right subtree. This guaranteed that the worst-case search time wasO(log n), where n is the number of nodes in the tree. Which of the following requirements wouldalso provide the same guarantee?(a) The number of nodes in each left subtree is within a factor of 2 of the number of nodesin the corresponding right subtree. Also, a node is allowed to have only one child ifthat child has no children.This tree has worst case height O(lg n).True FalseExplain:6.006 Final Exam Name 10(b) The number of leaves (nodes with no children) in each left subtree is within one of thenumber of leaves in the corresponding right subtree.This tree has worst case height O(lg n).True FalseExplain:6.006 Final Exam Name 11Problem 5. Height Balanced Trees [10 points]We define the height of a node in a binary tree as the number of nodes in the longest path from thenode to a descendant leaf. Thus the height of a node with no children is 1, and the height of anyother node is 1 plus the larger of the heights of its left and right children.We define height balanced trees as follows;• each node has a “height” field containing its height,• at any node, the height of its right child differs by at most one from the height of its left child.Finally we define Fib(i) as follows,Fib(0) = 1Fib(1) = 1Fib(i) = Fib(i − 1) + Fib(i − 2), for i ≥ 2.You may use without proof that Fib(n) ≥ 1.6nfor large n.Prove that there are at least Fib(h) nodes in a height balanced tree of height h, for all h ≥ 1.6.006 Final Exam Name 12Problem 6. Maintaining Medians [15 points]Your latest and
View Full Document
Unlocking...