DOC PREVIEW
MIT 6 006 - LECTURE NOTES

This preview shows page 1-2-3-4-30-31-32-33-34-61-62-63-64 out of 64 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 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 64 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 64 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 64 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 64 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 64 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 64 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 64 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 64 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 64 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 64 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 64 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 64 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.006- Introduction to Algorithms Lecture 10 Prof. Piotr IndykQuiz 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 1:2 2:3 123 1:3 132 312 1:3 213 2:3 231 321 A recipe for sorting n numbers 〈a1, a2, …, an〉$≥ ≤ - Branching direction depends on outcome of comparisons. - Nodes are suggested comparisons: i:j means compare ai to aj, for i, j ∈ {1, 2,…, n}. ≥ ≤ ≥ ≤ ≥ ≤ ≥ ≤ - Leaves are labeled with permutations corresponding to the outcome of the sorting.Decision-tree example 1:2 2:3 123 1:3 132 312 1:3 213 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. 9 ≥ 4 Sort 〈a1, a2, a3〉 = 〈 9, 4, 6 〉:$1:2Decision-tree example 1:2 2:3 123 1:3 132 312 1:3 213 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. 9 ≥ 6 Sort 〈a1, a2, a3〉 = 〈 9, 4, 6 〉:$Decision-tree example 1:2 2:3 123 1:3 132 312 1:3 213 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. 4 ≤ 6 Sort 〈a1, a2, a3〉 = 〈 9, 4, 6 〉:$Decision-tree example 1:2 2:3 123 1:3 132 312 1:3 213 2:3 231 321 Each leaf contains a permutation 〈π(1), π(2),…, π(n)〉 to indicate that the ordering aπ(1) ≤ aπ(2) ≤  ≤ aπ(n) has been established. 4 ≤ 6 ≤ 9 Sort 〈a1, a2, a3〉 = 〈 9, 4, 6 〉:$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 decision-tree 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 is mono. increasing) ≥ lg ((n/e)n) (Stirling’s formula) = n lg n – n lg e = Ω(n lg n) .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 using cumulative frequencies build sorted permutation 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}|Counting-sort example A: 4 1 3 4 3 B: 1 2 3 4 5 C: 1 2 3 4 one index for each possible key stored in ALoop 1: initialization A: 4 1 3 4 3 B: 1 2 3 4 5 C: 0 0 0 0 for i ← 1 to k do C[i] ← 0 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 3 B: 1 2 3 4 5 C: 0 0 0 1 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 3 B: 1 2 3 4 5 C: 1 0 0 1 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 3 B: 1 2 3 4 5 C: 1 0 1 1 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 3 B: 1 2 3 4 5 C: 1 0 1 2 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| 1 2 3 4Loop 2: count frequencies A: 4 1 3 4 3 B: 1 2 3 4 5 C: 1 0 2 2 for j ← 1 to n …


View Full Document

MIT 6 006 - LECTURE NOTES

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 LECTURE NOTES
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 LECTURE NOTES 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 LECTURE NOTES 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?