May 19 2011 6 006 Spring 2011 Final Exam Introduction to Algorithms Massachusetts Institute of Technology Professors Erik Demaine Piotr Indyk and Manolis Kellis Final 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 most progress This exam booklet contains 20 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 handwritten 8 12 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 7 10 2 8 40 8 10 3 3 15 9 15 4 10 10 10 5 10 11 20 6 10 Total Grader 180 Name Athena username Recitation Nick WF10 Nick WF11 Tianren WF12 David WF1 Joe WF2 Joe WF3a Michael WF3b 6 006 Final Exam Name 2 Problem 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 c T F Under the simple uniform hashing assumption the probability that three specific data elements say 1 2 and 3 hash to the same slot i e h 1 h 2 h 3 is 1 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 array in O n time in the worst case 3 6 006 Final Exam Name e T F The following array is a max heap 10 3 5 1 4 2 f T F R ADIX S ORT does not work correctly i e does not produce the correct output if we sort each individual digit using I NSERTION S ORT instead of C OUNTING S ORT 4 6 006 Final Exam Name g T F Given a directed graph G consider forming a graph G0 as follows Each vertex u0 G0 represents a strongly connected component SCC of G There is an edge u0 v 0 in G0 if there is an edge in G from the SCC corresponding to u0 to the SCC corresponding to v 0 Then G0 is 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 have w0 e w e 2 For any two vertices u v V any shortest path between u and v in G0 is also a shortest path in G 5 6 006 Final Exam i T F Name An optimal solution to a knapsack problem will always contain the object i with the greatest value to cost ratio vi ci j T F Every problem in NP can be solved in exponential time 6 6 006 Final Exam Name 7 Problem 2 Short answer 40 points 8 parts a Rank the following functions by increasing order of growth that is find an arrangement g1 g2 g3 g4 of the functions satisfying g1 O g2 g2 O g3 g3 O g4 For example the correct ordering of n2 n4 n n3 is n n2 n3 n4 f1 n 1 n f2 log nn f3 nn 1 2 f4 n log n log log n b Solve the following recurrences by giving tight notation bounds You do not need to justify your answers but any justification that you provide will help when assigning partial credit i T n 4T n 2 n2 log n ii T n 8T n 2 n log n iii T n 6006 T n 2 n 6006 6 006 Final Exam Name 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 sort ii Merge sort iii 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 comparison model Explain why or why not 8 6 006 Final Exam Name e Given n integers in the range 0 k describe how to preprocess these integers into a data structure that can answer the following query in O 1 time given two integers a and b how many integers fall within the range a b f Describe how any comparison based sorting algorithm can be made stable without affecting the running time by more than a constant factor 9 6 006 Final Exam Name g In dynamic programming we derive a recurrence relation for the solution to one subproblem in terms of solutions to other subproblems To turn this relation into a bottomup dynamic programming algorithm we need an order to fill in the solution cells in a table such that all needed subproblems are solved before solving a subproblem For each of the following relations give such a valid traversal order or if no traversal order is 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 heavy hitter 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 10 6 006 Final Exam Name 11 Problem 3 You are the computer 15 points 3 parts a Fill in the following grid with the correct subproblem solutions for this sequence …
View Full Document
Unlocking...