Administrivia, Lecture 4• HW #2 assigned this weekend, due Thurs Week 4• HWs will be due Thurs of Weeks 2, 4, 6, 7, 9, 10• HW #1 solutions should be posted tonight (TA’s have compiled them)• Reading for next week: Chapter 9.2-3 (linear-time selection), Chapter 33.3-4 (convex hull, closest-pair), Chapter 23 (minimum spanning trees)Divide and Conquer for Sorting (2.3/1.3)• Divide (into two equal parts)• Conquer (solve for each part separately)• Combine separate solutions• Mergesort– Divide into two equal parts– Sort each part using Mergesort (recursion!!!)– Merge two sorted subsequencesMerging Two Subsequences x[1]-x[2]- … - x[K] y[1]-y[2]- … - y[L]if y[i] > x[j] ⇒ y[i+1] > x[j]<< K+L-1 edges = # (comparisons) = linear timeMerge Sort Execution Example285 179 652 351 423310 861 254 450 520285179 652 351423310861 254 450 520285179 652 351423310861 254 450 520285179 652 351423310861 254 450 520310179 652 351423285861 254 450 520310179 652 351423285861 254 450 520310179652351423285861 254 450 520310179 351 652423285861 254 450 520310179 351 652423285861 254 450 520285 310 351 652423179861 254 450 520285 310 351 652423179861 254 450 520285310 351 652423179861254 450 520285 310 351 652423179861254 450 520285310 351 652423179861254 450 520285310 351 652423179861254450 520285310 351 652423179861254450 520285310 351 652423179861254 450 520285310 351 652254179423 450 520 861254 285 310 351 423179 450 520 652 861Recursion Tree1 2 3 4 5 6 7 81 3 5 8 2 4 6 71 5 3 85 1 3 84 7 2 67 4 6 2log n• n comparisons per level• log n levels• total runtime = n log nMaster Method (4. 3)Recurrence T(n) = a⋅T(n/b) + f(n)1) If for some ε > 0 then2) If then 3) If for some ε > 0 and a⋅ f(n/b)≤ c⋅ f(n) for some c < 1 then)()(log ε−=abnOnf)()(log abnnT Θ=)()(log abnnf Θ=)()(log ε+Ω=abnnf)log()(lognnnTabΘ=))(()(nfnTΘ=Master Method Examples• Mergesort T(n) = 2T(n/2) + Θ(n)• Strassen (28.2) T(n) = 7T(n/2) + Θ(n2)2)(2log2Casennn ⇒Θ==)log()( nnnTΘ=1)(281.081.27log2CasenOnn ⇒==−−ε)()()(807.27log2nnnT Θ≈Θ=Quicksort (7.1-7.2/8.1-8.2)• Sorts in place like insertion sort, unlike merge sort• Divide into two parts such that – elements of left part < elements of right part• Conquer: recursively solve for each part separately• Combine: trivial - do not do anythingQuicksort(A,p,r)if p < r then q ← Partition (A,p,r)Quicksort (A,p,q)Quicksort (A,q+1,r)//divide//conquer left//conquer rightDivide = PartitionPARTITION(A,p,r) //Partition array from A[p] to A[r] with pivot A[p]//Result: All elements ≤ original A[p] have index ≤ ix = A[p]i = p - 1j = r + 1repeat foreverrepeat j = j - 1 until A[j] ≤ xrepeat i = i +1 until A[i] ≥ xif i < j then exchange A[i] ↔ A[j]else return jHow It Works9 7 6 15 16 5 10 11ij97 6 15 16 5 10 11ij97 6 15 16 5 10ij1197 6 15 16 5 10ij111097 6 15 16 5ij111097 6 15 16 5ij111097 6 15 16 5ij111097 6 15 16 5ij111097 6 15 16 5ij11105* 7 6 15 169*ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 169ij11105 7 6 15 16911left right97 6 15 16 5 10 11ij105 7 6 15 16 9 11left right105 7 6 15 16 9 11left right1057 6 15 16 9 11left right1057 6 15 16 9 11left rightji1057 6 15 16 9 11left rightji1057 6 15 16 9 11left rightji1057 6 15 16 9 11left rightji1057 6 15 16 9 11left rightji105 7 6 15 16 9 11left right105 6 7 15 16 9 11left right105 6 7 15 16 9 11left right105 6 71516 9 11left right105 6 71516 9 11left rightjj105 6 71516 9 11left rightji105 6 7 11* 16 915*left rightji105 6 7 11 16 915left rightji105 6 7 11 16 915left rightji165 6 7 11 10 915left rightji165 6 7 11 10 915left rightj i165 6 7 11 10 9 15left right165 6 7 9 10 11 15left right155 6 7 9 10 11 16left right155 6 7 9 10 11 16Runtime of Quicksort• Worst case: – every time nothing to move– pivot = left (right) end of subarray– O(n2)012345678912345678980989nRecursion Tree of QSortRuntime of Quicksort• Best case: – every time partition in (almost) equal parts – no worse than in given proportion– O(n log n)• Average case = ?What is the DQ Recurrence for QSort?• t(n) = Θ(n) + 1/n ∑j = 1 to n(t(j-1) + t(n-j))pivots pivots equiprobable lengths of subproblems= Θ(n) + 2/n ∑k = 0 to n-1t(k)• Guess t(n) ∈ O(n log n)• t(n) ≤ Θ(n) + 2/n [∑i=2 to n-1c i log i] ≤ c n log n – cn/242^log22^...^24loglog22^logloglog1111000nnnxexxxdxxiikkBoundennennienk−≤−=≤∫∑∑+−+=−=Another QSort Analysis (Shift / Cancel)• (1) T(n) = n-1 + 2/n ∑j = 1 to n-1T(i), n ≥ 2, T(1) = 0• (2) T(n+1) = n+1 - 1 + 2/(n+1) ∑j = 1 to nT(i) (1) à (3) nT(n) = n(n-1) + 2 ∑j = 1 to n-1T(i)(2) à (4) (n+1)T(n+1) = (n+1)n + 2 ∑j = 1 to nT(i)(4) - (3) à (n+1)T(n+1) – nT(n) = 2n + 2T(n) à T(n+1) = (n+2)/(n+1) T(n) + 2n/(n+1)à T(n+1) ≤ (n+2)/(n+1) T(n) + 2Shift / Cancel (cont.)Unroll: Hn= 1 + ½ + 1/3 + …+ 1/n = ln n + + O(1/n)γ = Euler’s constant = 0.577…⇒ T(n) ≤ 2(n+1) (ln n + γ – 3/2) + O(1)⇒ T(n) ∈ O(n log n))23)(1(2)31...11111()1(231...211111(2)34..1...21111111(2)))34(...212(12(12)(1 −+=++−++++=+++−++−++++=+++−−−++−++++=+−−+−+++≤+nHnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnTRandomized Analysis of QSort• Probability space– Set Ω of elementary events ≡ experiment outcomes– Family F of subsets of Ω, called events– Probability measure Pr, real-valued function on members of F– where A ⊆ Ω, A ∈ F à Ac∈ FF closed under union, intersectionFor all A ∈ F, 0 ≤ Pr(A) ≤ 1Pr(Ω) = 1For disjoint events A1, A2, ... Pr(U Ai) = ∑Pr(Ai)• Random variable is a function from elements of Ω into ℜ– e.g., event (X = x) ≡ set of elements of Ω for which X assumes the fixed value x• For integer-valued r.v. X, expectation E[X] = ∑iPr(X=i)Randomized Analysis of QSort (cont.)• At each level, we compare each element to the splitter in its partition• Def. A successful pivot p satisfies n/8 < p < 7n/8• Three facts– (1) E[Σ Xi] = Σ E[Xi] linearity of expectation– (2) If Pr(Heads) is q, expected # tosses up to and including first Head is 1/q // family size puzzle– (3) Pr(UiAi) ≤ ΣiPr(Ai) prob of union ≤ sum of probs• Given that