Introduction to Algorithms May 19, 2011Massachusetts Institute of Technology 6.006 Spring 2011Professors Erik Demaine, Piotr Indyk, and Manolis Kellis Final ExamFinal Exam• Do not open this exam booklet until 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.• You have 180 minutes to earn 180 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 exam booklet contains 20 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 handwritten, 81200× 1100or A4 crib sheets(both sides). No calculators or programmable devices are permitted. No cell phones or othercommunications devices 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 7 – 102 8 40 8 – 103 3 15 9 – 154 – 10 10 – 105 – 10 11 – 206 – 10 Total 180Name:Athena username:Recitation:NickWF10NickWF11TianrenWF12DavidWF1JoeWF2JoeWF3aMichaelWF3b6.006 Final Exam Name 2Problem 1. True or false [30 points] (10 parts)For each of the following questions, circle either T (True) or F (False). Explain your choice.(Your explanation is worth more than your choice of true or false.)(a) T F For all positive f(n), f(n) + o(f(n)) = Θ(f(n)).(b) T F For all positive f(n), g(n) and h(n), if f (n) = O(g(n)) and f(n) = Ω(h(n)),then g(n) + h(n) = Ω(f (n)).6.006 Final Exam Name 3(c) T F Under the simple uniform hashing assumption, the probability that three specificdata elements (say 1, 2 and 3) hash to the same slot (i.e., h(1) = h(2) = h(3)) is1/m3, where m is a number of buckets.(d) T F Given an array of n integers, each belonging to {−1, 0, 1}, we can sort the arrayin O(n) time in the worst case.6.006 Final Exam Name 4(e) T F The following array is a max heap: [10, 3, 5, 1, 4, 2].(f) T F RADIX SORT does not work correctly (i.e., does not produce the correct output)if we sort each individual digit using INSERTION SORT instead of COUNTINGSORT.6.006 Final Exam Name 5(g) T F Given a directed graph G, consider forming a graph G0as follows. Each vertexu0∈ G0represents a strongly connected component (SCC) of G. There is anedge (u0, v0) in G0if there is an edge in G from the SCC corresponding to u0tothe SCC corresponding to v0.Then G0is a directed acyclic graph.(h) T F Consider two positively weighted graphs G = (V, E, w) and G0= (V, E, w0)with the same vertices V and edges E such that, for any edge e ∈ E, we havew0(e) = w(e)2.For any two vertices u, v ∈ V , any shortest path between u and v in G0is also ashortest path in G.6.006 Final Exam Name 6(i) T F An optimal solution to a knapsack problem will always contain the object i withthe greatest value-to-cost ratio vi/ci.(j) T F Every problem in NP can be solved in exponential time.6.006 Final Exam Name 7Problem 2. Short answer [40 points] (8 parts)(a) Rank the following functions by increasing order of growth; that is, find an arrange-ment g1, g2, g3, g4of the functions satisfying g1= O(g2), g2= O(g3), g3= O(g4).(For example, the correct ordering of n2, n4, n, n3is n, n2, n3, n4.)f1= (n!)1/nf2= log nnf3= nn1/2f4= n log n log log n(b) Solve the following recurrences by giving tight Θ-notation bounds. You do not needto justify your answers, but any justification that you provide will help when assigningpartial credit.i. T (n) = 4T (n/2) + n2log nii. T (n) = 8T (n/2) + n log niii. T (n) =√6006 · T (n/2) + n√60066.006 Final Exam Name 8(c) Give a recurrence T (n) = ··· for the running time of each of the following algorithms,along with the asymptotic solution to that recurrence:i. Insertion sortii. Merge sortiii. 2D peak finding (the fastest algorithm we’ve seen)(d) Could a binary search tree be built using o(n lg n) comparisons in the comparisonmodel? Explain why or why not.6.006 Final Exam Name 9(e) Given n integers in the range 0 . . . k, describe how to preprocess these integers into adata structure that can answer the following query in O(1) time: given two integers aand b, how many integers fall within the range a . . . b?(f) Describe how any comparison-based sorting algorithm can be made stable, withoutaffecting the running time by more than a constant factor.6.006 Final Exam Name 10(g) In dynamic programming, we derive a recurrence relation for the solution to one sub-problem in terms of solutions to other subproblems. To turn this relation into a bottom-up dynamic programming algorithm, we need an order to fill in the solution cells in atable, such that all needed subproblems are solved before solving a subproblem. Foreach of the following relations, give such a valid traversal order, or if no traversal orderis possible for the given relation, briefly justify why.i. A(i, j) = F (A(i, j − 1), A(i − 1, j − 1), A(i − 1, j + 1))ii. A(i, j) = F (A(min{i, j}−1, min{i, j}−1), A(max{i, j}−1, max{i, j}−1))iii. A(i, j) = F (A(i −2, j − 2), A(i + 2, j + 2))(h) Consider an array A[1 . . . n] of integers in the range 1 . . . n2. A number a is a heavyhitter in A if a occurs in A at least n/2 times.Give an efficient algorithm that finds all heavy hitters in a given array A.6.006 Final Exam Name 11Problem 3. You are the computer [15 points] (3 parts)(a) Fill in the following grid with the correct subproblem solutions for this sequence align-ment problem with these weights: 0 for mutation, 1 for insertion or deletion, and 3 fora match (the goal is to maximize the sum of the weights). Here “ATC” is the startingsequence and “TCAG” is the ending sequence.– – A T C– 0TCAGWhat is the optimal alignment?(b) Draw a max-heap on the following set of integers: {2, 3, 5, 7, 11, 13, 17}. (You do notneed to use the Build-Heap algorithm.)6.006 Final Exam Name 12(c) Compute3√6006 using two iterations of Newton’s method, i.e., fill out
View Full Document
Unlocking...