DOC PREVIEW
MIT 6 006 - Final Exam

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction to Algorithms December 14, 2009Massachusetts Institute of Technology 6.006 Fall 2009Professors Srini Devadas and Constantinos (Costis) Daskalakis Final ExamFinal 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 mostprogress.• This quiz booklet contains 13 pages, including this one. Two extra sheets of scratch paperare attached. Please detach them before turning in your quiz at the end of the exam period.• This quiz is closed book. You may use three 81200× 1100or A4 crib sheets (both sides). Nocalculators or programmable devices are permitted. No cell phones or other communicationsdevices are permitted.• Write your solutions in the space provided. If you need more space, write on the back of thesheet 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 citeknown results.• 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 10 30 5 1 202 1 10 6 1 153 1 10 7 1 204 1 20 8 3 25Total 150Name:6.006 Final Exam Name 2Problem 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, wehash two new keys k1and k2. Under the simple uniform hashing assumption, the probabilitythat k1and k2are hashed into the same table location is exactly 1/m with no dependence onthe number of keys n.Answer = True False2.Under the uniform hashing assumption, if we use a hash table of size m with open addressingto hash 3 keys, the probability that the third inserted key needs exactly three probes beforebeing inserted into the table is exactly2m(m−1).Answer = True False3.We use a hash table of size m with open addressing to hash n items. Under the uniformhashing assumption, the expected cost to insert another element into the table is at most1 + α, where α = n/m is the average load.Answer = True False4.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 Unknown5.There exists a polynomial-time algorithm for finding longest simple paths in weighted di-rected acyclic graphs.Answer = True False Unknown6.006 Final Exam Name 36.Every search problem in NP can be solved in exponential time.Answer = True False Unknown7.If there are negative edges in a graph but no negative cycles, Dijkstra’s algorithm still runscorrectly.Answer = True False8.In a shortest path problem, if each arc length increases by k units, shortest path distancesincrease by a multiple of k.Answer = True False9.For any two functions f and g, we always have either f = O(g) or g = O(f).Answer = True False10.Dijkstra’s shortest path algorithm runs in O(V3) time.Answer = True False6.006 Final Exam Name 4Problem 2. Data Structures [10 points]Design a data structure that keeps a sequence of real numbers S = (x1, ..., xn), and supports thefollowing operations in O(log n) time, where n is the current length of the sequence:•Insert(y, i): inserts y between xiand xi+1•Sum(i, j): compute the sumjXt=ixtAssume that the data structure is initially empty.6.006 Final Exam Name 5Problem 3. Binary Trees [10 points]Consider the family of binary trees of n nodes with the following invariant for every node. If n1and n2are 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 arigorous argument or a counter-example.6.006 Final Exam Name 6Problem 4. kthminimum in min-heap [20 points]Present an O(k log k) time algorithm to return the kthminimum element in a min-heap H of size n,where 1 ≤ k ≤ n. Partial credit will be given to less efficient solutions provided your complexityanalysis is accurate.6.006 Final Exam Name 7Problem 5. 2-Satisfiability [20 points]The 2-SAT problem is defined as follows: There are n Boolean variables x1, . . . , xn, and a set ofm 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, theclause 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 satisfyingassignment for Example 2. Variable assignments that are required to satisfy some of the clausesconflict with assignments that are required to satisfy other clauses in this case. The 2-SAT problemis to find a satisfying assignment, if one exists. We note that 2-SAT (unlike 3-SAT) can be solvedin polynomial time.Here we are only concerned with a sufficiency check for unsatisfiability. That is, we want to devisea graph-based algorithm that checks if a given set of clauses is unsatisfiable. We want this checkto be as efficient and as general as possible. To do this, we will represent the 2-SAT problem as agraph. The two graphs for the examples above are shown below in Figures 1 and 2. Each graph has2n vertices: there are two vertices for every variable corresponding to the true and complementedforms, namely, xi= TRUE and xi= FALSE for each xi. The edges of the graph represent theimplied assignments for variables. For example, for every clause of the form (x1+ x2), we havean edge from x1= FALSE to x2= FALSE and an edge from x2= TRUE to x1= TRUE (If weset x1= FALSE, then we require x2= FALSE for this clause to be satisfied, similarly the othercase).x1= TRUEx3= TRUE x3= FALSEx4= TRUE x2= TRUEx2= FALSEx4= FALSEx1= FALSE(x1+x2)(x1+ x4)(x3+ x4)(x2+ x4)Figure 1: Example 1 satisfiable6.006 Final Exam Name 8x1= TRUEx3=


View Full Document

MIT 6 006 - Final Exam

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Final Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Exam 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?