May 21 2008 6 006 Spring 2008 Final Exam Introduction to Algorithms Massachusetts Institute of Technology Professors Srini Devadas and Erik Demaine Final Exam Do not open this exam booklet until you are directed to do so Read all the instructions on this 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 earn 180 points This exam booklet contains 24 pages including this one Two extra sheets of scratch paper are attached Please detach them before turning in your exam at the end of the exam period 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 Write your solutions in the space provided If you need more space write on the back of the sheet containing the problem Do not put part of the answer to one problem on the back of the 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 cite known results 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 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 Grader Problem Parts Points Grade 1 1 10 7 2 10 2 10 40 8 2 10 3 1 10 9 1 10 4 2 10 10 3 15 5 1 10 11 4 20 6 2 15 12 4 20 Total Grader 180 Name Circle your recitation time Hueihan Jhuang 10AM 11AM Victor Costan 2PM 3PM 6 006 Final Exam Name 2 Problem 1 Asymptotics 10 points For each pair of functions f n and g n in the table below write O or in the appropriate space depending on whether f n O g n f n g n or f n g n If there is more than one relation between f n and g n write only the strongest one The first line is a demo solution We use lg to denote the base 2 logarithm n lg2 n 2lg 2 n lg n nlg 3 n n lg n n2 O 6 006 Final Exam Name 3 Problem 2 True or False 40 points 10 parts Decide whether these statements are True or False You must briefly justify all your answers to receive 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 recurrence E n 2 E n 1024 O 1 True False Explain 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 recurrence B n 2 B n 4 O 1 True False Explain 6 006 Final Exam Name 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 False Explain d Given an undirected graph it can be tested to determine whether or not it is a tree in O V E time A tree is a connected graph without any cycles True False Explain 4 6 006 Final Exam Name e The Bellman Ford algorithm applies to instances of the single source shortest path problem which do not have a negative weight directed cycle but it does not detect the existence of a negative weight directed cycle if there is one True False Explain f The topological sort of an arbitrary directed acyclic graph G V E can be computed in linear time True False Explain 5 6 006 Final Exam Name g We know of an algorithm to detect negative weight cycles in an arbitrary directed graph in O V E time True False Explain h We know of an algorithm for the single source shortest path problem on an arbitrary graph with no negative weights that works in O V E time True False Explain 6 6 006 Final Exam Name i To delete the ith node in a min heap you can exchange the last node with the ith node then do the min heapify on the ith node and then shrink the heap size to be one less the original size True False Explain j Generalizing Karatsuba s divide and conquer algorithm by breaking each multiplicand into 3 parts and doing 5 multiplications improves the asymptotic running time True False Explain 7 6 006 Final Exam Name 8 Problem 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 an arbitrary order In computing the union the algorithm must remove any duplicate elements that appear 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 time algorithm 6 006 Final Exam Name 9 Problem 4 Balanced Trees 10 points In the definition of an AVL tree we required that the height of each left subtree be within one of the height of the corresponding right subtree This guaranteed that the worst case search time was O log n where n is the number of nodes in the tree Which of the following requirements would also provide the same guarantee a The number of nodes in each left subtree is within a factor of 2 of the number of nodes in the corresponding right subtree Also a node is allowed to have only one child if that child has no children This tree has worst case height O lg n True False Explain 6 006 Final Exam Name b The number of leaves nodes with no children in each left subtree is within one of the number of leaves in the corresponding right subtree This tree has worst case height O lg n True False Explain 10 6 006 Final Exam Name 11 Problem 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 the node to a descendant leaf Thus the height of a node with no children is 1 and the height of any other 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 1 …
View Full Document
Unlocking...