December 14 2009 6 006 Fall 2009 Final Exam Introduction to Algorithms Massachusetts Institute of Technology Professors Srini Devadas and Constantinos Costis Daskalakis 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 150 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 This quiz booklet contains 13 pages including this one Two extra sheets of scratch paper are attached Please detach them before turning in your quiz at the end of the exam period 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 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 10 30 5 1 20 2 1 10 6 1 15 3 1 10 7 1 20 4 1 20 8 3 25 Total Name 150 Grader 6 006 Final Exam Name 2 Problem 1 True or False 30 points 10 parts For each of the following questions circle either True False or Unknown 1 After hashing n keys into a hash table of size m that uses chaining to handle collisions we hash two new keys k1 and k2 Under the simple uniform hashing assumption the probability that k1 and k2 are hashed into the same table location is exactly 1 m with no dependence on the number of keys n Answer True False 2 Under the uniform hashing assumption if we use a hash table of size m with open addressing to hash 3 keys the probability that the third inserted key needs exactly three probes before 2 being inserted into the table is exactly m m 1 Answer True False 3 We use a hash table of size m with open addressing to hash n items Under the uniform hashing assumption the expected cost to insert another element into the table is at most 1 where n m is the average load Answer True False 4 There is a polynomial time algorithm for the Knapsack problem if all items have size in 0 1 regardless of the bits required to describe their values and the size of the knapsack Answer True False Unknown 5 There exists a polynomial time algorithm for finding longest simple paths in weighted directed acyclic graphs Answer True False Unknown 6 006 Final Exam Name 3 6 Every search problem in NP can be solved in exponential time Answer True False Unknown 7 If there are negative edges in a graph but no negative cycles Dijkstra s algorithm still runs correctly Answer True False 8 In a shortest path problem if each arc length increases by k units shortest path distances increase by a multiple of k Answer True False 9 For any two functions f and g we always have either f O g or g O f Answer True False 10 Dijkstra s shortest path algorithm runs in O V 3 time Answer True False 6 006 Final Exam Name 4 Problem 2 Data Structures 10 points Design a data structure that keeps a sequence of real numbers S x1 xn and supports the following operations in O log n time where n is the current length of the sequence Insert y i inserts y between xi and xi 1 Sum i j compute the sum j X xt t i Assume that the data structure is initially empty 6 006 Final Exam Name 5 Problem 3 Binary Trees 10 points Consider the family of binary trees of n nodes with the following invariant for every node If n1 and n2 are the number of nodes in the left and the right subtree respectively then max n1 n2 min n1 n2 2 1 Is the height of these trees bounded by O log n Justify your answer with a rigorous argument or a counter example 6 006 Final Exam Name 6 Problem 4 k th minimum in min heap 20 points Present an O k log k time algorithm to return the k th minimum element in a min heap H of size n where 1 k n Partial credit will be given to less efficient solutions provided your complexity analysis is accurate 6 006 Final Exam Name 7 Problem 5 2 Satisfiability 20 points The 2 SAT problem is defined as follows There are n Boolean variables x1 xn and a set of m clauses Each clause has two variables which are either in true xi or complemented xi form Here are two examples 1 x1 x2 x1 x4 x3 x4 x2 x4 is satisfiable 2 x1 x2 x2 x3 x3 x1 x1 x4 x4 x1 is not satisfiable For a 2 SAT formula to be satisfiable every clause should be satisfiable To satisfy a clause x1 x2 we can set x1 TRUE and or x2 FALSE If x1 FALSE and x2 TRUE the clause is not satisfied Example 1 is a satisfiable set of clauses because we can set x1 TRUE x2 TRUE x3 FALSE and x4 TRUE to satisfy all the clauses There is no satisfying assignment for Example 2 Variable assignments that are required to satisfy some of the clauses conflict with assignments that are required to satisfy other clauses in this case The 2 SAT problem is to find a satisfying assignment if one exists We note that 2 SAT unlike 3 SAT can be solved in polynomial time Here we are only concerned with a sufficiency check for unsatisfiability That is we want to devise a graph based algorithm that checks if a given set of clauses is unsatisfiable We want this check to be as efficient and as general as possible To do this we will represent the 2 SAT problem as a graph The two graphs for the examples above are shown below in Figures 1 and 2 Each graph has 2n vertices there are two vertices for every variable corresponding to the true and complemented forms namely xi TRUE and xi FALSE for each xi The edges of the graph represent the implied assignments for variables For example for every clause of the form x1 x2 we have an edge from x1 FALSE to x2 FALSE and an edge from x2 TRUE to x1 TRUE If we set x1 FALSE then we require x2 FALSE for this clause to be satisfied similarly the other case x1 TRUE x1 FALSE …
View Full Document
Unlocking...