6 006 Introduction to Algorithms Lecture 10 Prof Piotr Indyk Quiz Rules 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 120 minutes to earn 120 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 X 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 This quiz is closed book You may use one 8 1 11 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 re deriving 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 At participating locations only Do not use while sleeping Read label before using Details inside Harmful if swallowed Menu sorting ctd Show that n lg n is the best possible running time for a sorting algorithm Design an algorithm that sorts in n time Hint maybe the models are different Comparison sort All the sorting algorithms we have seen so far are comparison sorts only use comparisons to determine the relative order of elements E g insertion sort merge sort heapsort The best running time that we ve seen for comparison sorting is O n lg n Is O n lg n the best we can do via comparisons Decision trees can help us answer this question Decision tree A recipe for sorting n numbers a1 a2 an Nodes are suggested 2 3 comparisons i j means 123 1 3 compare ai to aj for i j 1 2 n 132 1 2 312 213 1 3 2 3 231 Branching direction depends on outcome of comparisons Leaves are labeled with permutations corresponding to the outcome of the sorting 321 Decision tree example Sort a1 a2 a3 9 4 6 1 2 9 4 2 3 123 1 3 213 1 3 132 312 2 3 231 321 Each internal node is labeled i j for i j 1 2 n The left subtree shows subsequent comparisons if ai aj The right subtree shows subsequent comparisons if ai aj Decision tree example Sort a1 a2 a3 9 4 6 1 2 2 3 123 1 3 213 1 3 132 312 9 6 2 3 231 321 Each internal node is labeled i j for i j 1 2 n The left subtree shows subsequent comparisons if ai aj The right subtree shows subsequent comparisons if ai aj Decision tree example Sort a1 a2 a3 9 4 6 1 2 2 3 123 1 3 213 1 3 132 312 4 6 2 3 231 321 Each internal node is labeled i j for i j 1 2 n The left subtree shows subsequent comparisons if ai aj The right subtree shows subsequent comparisons if ai aj Decision tree example Sort a1 a2 a3 9 4 6 1 2 2 3 123 1 3 213 1 3 132 312 2 3 231 321 4 6 9 Each leaf contains a permutation 1 2 n to indicate that the ordering a 1 a 2 a n has been established Decision tree model A decision tree can model the execution of any comparison sort One tree for each input size n A path from the root to the leaves of the tree represents a trace of comparisons that the algorithm may perform The running time of the algorithm the length of the path taken Worst case running time height of tree Lower bound for decisiontree sorting Theorem Any decision tree that can sort n elements must have height n lg n Proof The tree must contain n leaves since there are n possible permutations A height h binary tree has 2h leaves Thus 2h n h lg n lg n e n n lg n n lg e n lg n lg is mono increasing Stirling s formula Sorting in linear time Counting sort No comparisons between elements Input A 1 n where A j 1 2 k Output B 1 n a sorted permutation of A implicitly we also determine the permutation transforming A into B Auxiliary storage C 1 k Counting sort for i 1 to k do C i 0 for j 1 to n do C A j C A j 1 for i 2 to k do C i C i C i 1 for j n downto 1 do B C A j A j C A j C A j 1 store in C the frequencies of the different keys in A i e C i key i now C contains the cumulative frequencies of different keys in A i e C i key i using cumulative frequencies build sorted permutation Counting sort example one index for each possible key stored in A A B 1 2 3 4 5 4 1 3 4 3 1 C 2 3 4 Loop 1 initialization A 1 2 3 4 5 4 1 3 4 3 B for i 1 to k do C i 0 C 1 2 3 4 0 0 0 0 Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 0 0 0 1 B for j 1 to n do C A j C A j 1 C i key i Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 0 1 B for j 1 to n do C A j C A j 1 C i key i Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 1 1 B for j 1 to n do C A j C A j 1 C i key i Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 1 2 B for j 1 to n do C A j C A j 1 C i key i Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 2 2 B for j 1 to n do C A j C A j 1 C i key i Loop 2 count frequencies A 1 2 3 4 5 4 1 3 4 3 C 1 2 3 4 1 0 2 2 …
View Full Document
Unlocking...