CS代写 Topic 4: Divide-and-Conquer, Recurrence

Topic 4: Divide-and-Conquer, Recurrence
􏰀 Divide & Conquer: MergeSort (CLRS p30-37)
􏰀 Solving Recurrence Relations (iterated substitution, recurrence tree,
guess and test) (CLRS p83-92)

Copyright By PowCoder代写 加微信 powcoder

􏰀 Solving Recurrences (Cont’d) Master Theorem (CLRS p.93-97)

Divide and Conquer and recursive programs
􏰀 A useful design technique for algorithms is divide-and-conquer
􏰀 These algorithms are often recursive and consist of the following
three steps: 􏰀 Divide:
􏰀 If the input size is very small (base case) then solve the problem using a simple method.
􏰀 else, divide the input into two or more disjoint (smaller) pieces & recursively solve the subproblems
􏰀 Conquer: Leverage on the solutions for the subproblems to get a solution for the original problem.
􏰀 To analyze (the running time of) a recursive program we express their running time as a recurrence
􏰀 We then solve the recurrence to find a closed form for the running time of the algorithm.
Topic 4: Divide-and-Conquer, Recurrence

Topic 4: Divide-and-Conquer, Recurrence
lo ≤ mid ≤ hi
A[lo, mid] and A[mid + 1, hi] sorted
A[lo, hi] sorted
Merge runs in O(n) time; the details are not particularly relevant here.
Merge-Sort(A; lo, hi) if lo < hi then mid = ⌊(lo + hi)/2⌋ Merge-Sort(A; lo, mid) Merge-Sort(A; mid + 1, hi) Merge(A; lo, mid, hi) Merge-Sort Merge(A; lo, mid, hi) **pre-condition: **pre-condition: **post-condition: Topic 4: Divide-and-Conquer, Recurrence Merge sort, the big idea — divide-and-conquer: 􏰀 Divide the whole list into 2 sublists of equal size; 􏰀 Recursively merge sort the 2 sublists; 􏰀 Combine the 2 sorted sublists into a sorted list. 􏰀 An example: 1 2 3 4 5 6 7 8 9 10 11 12 13 A [31 23 01 17 19 28 09 03 13 15 22 08 29] Merge sort — Example: Topic 4: Divide-and-Conquer, Recurrence 31 23 01 17 19 28 09 03 13 15 22 08 29 31 23 01 17 19 28 09 03 13 15 22 08 29 31 23 01 17 01 17 23 31 01 09 17 19 23 28 31 03 08 13 15 22 29 01 03 08 09 13 15 17 19 22 23 28 29 31 Recurrence relations — merge sort analysis 􏰀 MergeSort: 􏰀 Divide the whole list into 2 sublists of equal size; recursively sort each 􏰀 Merge the 2 sorted sublists into a sorted list. 􏰀 Let T (n) denote #KC (# of key comparisons) for a list of size n 􏰀 Assumptions: 􏰀 n (number of keys in the whole list) is a power of 2; This makes the analysis easier (since each time we are dividing by 2) 􏰀 Deriving recurrence relation: 􏰀 Merge sort on 2 sublists 2 × T(n2 ) 􏰀 Assembling needs n − 1 KC (in WC, the worst case) (it actually takes n KC; but the code can be easily revised so that n − 1 KC would be sufficient) 􏰏0 , ifn=1 􏰀 T(n)= (n−1)+2·T(n2) , otherwise 􏰀 How to solve this? Topic 4: Divide-and-Conquer, Recurrence Recurrence relations 􏰀 How to analyze Merge-Sort or any other recursive program? 􏰀 Write the running time as a recursive function of input size 􏰀 Recurrence relation: A relation defined recursively — in terms of itself, e.g., 􏰎 1, if n = 1 f(n)= n+f(n−1), ifn≥2 􏰀 Must have base case and general case. 􏰀 They arise in the analysis of Divide-and-Conquer algorithms 􏰀 How are recurrences solved? 1. iterated substitution/replacement method 2. recurrence tree method 3. Guess and Test method 4. master theorem method Topic 4: Divide-and-Conquer, Recurrence 1- Iterated Substitution 􏰎 1, if n = 1 Consider a simple example f(n) = n+f(n−1), if n ≥ 2 Particular cases: n1234567 f(n) 1 2+1 3+3 4+6 5+10 6+15 7+21 1 3 6 10 15 21 28 General case: f(n) = n+f(n−1) = n+(n−1)+f(n−2) = n+(n−1)+(n−2)+f(n−3) = n+(n−1)+(n−2)+(n−3)+f(n−4) = ... = n+(n−1)+(n−2)+(n−3)+...+2+f(1) n Therefore, we guess that f(n) = 􏰁 i i=1 This is NOT a proof, yet. We prove our guess by induction. Topic 4: Divide-and-Conquer, Recurrence Iterated substitution: example (cont’d) 􏰀 Prove that f(n) = 􏰁 i by induction. i=1 􏰀 Basecase: n=1. f(1)=1bydefinition,and􏰁1i=1i=1. 􏰀 Inductive step: Assume f(k) = 􏰁 i, for some natural k ≥ 1. Want to show i=1 f (k + 1) = 􏰁 i by using the recurrence relation (only). i=1 f(k+1)=(k+1)+f(k)=(k+1)+􏰁i= 􏰁i. 􏰒 f(n) = 􏰊i = n(n+1),n ≥ 1. k k+1 i=1 i=1 Topic 4: Divide-and-Conquer, Recurrence i=1 Proof by induction (exercise). 􏰀 n(n+1) is the closed form for the recurrence. 2 􏰀 You NEED to get the closed forms, as simple as possible! Recurrence relations — merge sort analysis 􏰀 Merge sort recall: 􏰀 Divide the whole list into 2 sublists of equal size; 􏰀 Recursively merge sort the 2 sublists; 􏰀 Combine the 2 sorted sublists into a sorted list. 􏰀 Assumptions: 􏰀 n is a power of 2, which makes the analysis easier (since each time we are dividing by 2) 􏰀 Let T(n) denote #KC for a list of size n 􏰀 Deriving recurrence relation: 􏰀 Merge sort on 2 sublists 2 × T(n2 ) 􏰀 Assembling needs n − 1 KC (in the WC) 􏰏0 , ifn=1 􏰀 T(n)= (n−1)+2·T(n2) , otherwise 􏰀 Solving recurrence relation: Topic 4: Divide-and-Conquer, Recurrence Topic 4: Divide-and-Conquer, Recurrence Merge sort analysis — solving the recurrence relation 􏰀 Particular case: T(1) = 0, T(2) = 1, ... 􏰀 General case: T(n) = (n−1)+2×T(n) 􏰗2􏰘 = (n−1)+2× (n2 −1)+2×T(n4) Solving Merge Sort (Cont’d) 􏰀 We assume n=2k so: T(2k) =(2k−1)+2×T(2k−1) −1)+2×􏰗(2k−1 −1)+2×T(2k−2)􏰘 −1)+(2k −2)+22 ×T(2k−2) −1)+(2k −2)+22 ×􏰗(2k−2 −1)+2×T(2k−3)􏰘 −1)+(2k −2)+(2k −22)+23 ×T(2k−3) −20)+(2k −21)+(2k −22)+23 ×T(2k−3) −20)+(2k −21)+(2k −22)+(2k −23)+24 ×T(2k−4) −20)+(2k −21)+(2k −22)+...+(2k −2k−1)+2k ×T(2k−k) −20)+(2k −21)+(2k −22)+...+(2k −2k−1) = k×2k−􏰁k−12i = (k−1)2k +1 byapplying􏰁k−12i =2k −1 1. Variable substitution makes guessing easy ... 2. In recurrence solving always assume n being some power whenever necessary (ignore floor and ceiling). 3. Prove by induction. 4. Need to transform back to original variable. Since n = 2k, we have k = lgn. So, T(n) = n(lgn−1)+1. Topic 4: Divide-and-Conquer, Recurrence Closed form proof by induction: 􏰀 􏰎 0 if n = 1 Recurrence: T(n)= (n−1)+2×T(n2) if n≥2 Guessedclosedform: T(n)=n(lgn−1)+1,n≥1 􏰀 Assumingn=2k,k≥0 􏰀 Basecase: T(1)=0andindeed1(lg(1)−1)+1=0. 􏰀 Inductive step: Assuming that T(2k) = 2k(k − 1) + 1, k ≥ 0, want to show T(2k+1) = 2k+1k + 1. By recurrence relation, T(2k+1) = (2k+1 − 1) + 2 × T(2k) = (2k+1 −1)+2k+1(k−1)+2 = k2k+1+1. 􏰒 􏰀 Extending to n which isn’t a power of 2 is just tedious: if n is not a powerof2,∃integerks.t. n≤2k <2n. So: T(n)≤T(2k)= 2k(k−1)+1 ≤ (2n)·(lg(2n)−1)+1 = 2nlg(n)+1 = O(nlog(n)). Topic 4: Divide-and-Conquer, Recurrence Running Time Analysis: 􏰀 We now wish to deduce that WC running time is Θ(n log n) 􏰀 Which direction is obvious? 􏰀 Lower bound: if each KC takes one “unit of time” then our running time is n(lg(n)−1)+1 ≥ 12nlg(n) ∈ Ω(nlg(n)) 􏰀 Upper bound: Merge takes O(n) times. So ∃c1 such that its running time ≤ c1n. 􏰀 Merge-Sort takes O(1) time in the base case and O(1) for the two recursive calls to make. 􏰀 Hence, if R(n) denotes the running time of Merge-Sort on n-size input, we have 􏰎 c3, if n = 1 R(n)= c1·n+c2+2R(n2), ifn≥2 􏰀 Set C to be any number ≥ c1 + c2 + c3 and we get 􏰎 C, if n = 1 R(n) ≤ Cn + 2R(n2 ), if n ≥ 2 and this recursion solves to C · n(lg(n)). 􏰀 Conclusion: merge sort WC running time is Θ(n log n). Topic 4: Divide-and-Conquer, Recurrence Conclusions 􏰀 Divide-and-conquer algorithm often recursive 􏰀 Analysis of recursive algorithm =⇒ solving recurrence An exercise: 􏰀 Examine the running time of QZ(n) Proc QZ(n) if n>1 then
a = n × n + 37
b = a × QZ( n2 )
return QZ(n2)×QZ(n2)+n
return n×n
􏰀 If we only consider arithmetic operations then: 􏰎 1 if n = 1
T(n)= 3QZ(n2)+5 ifn≥2
􏰀 Again, we use Iterated Substitution to obtain a proper guess
􏰀 Then we prove our guess by induction
Topic 4: Divide-and-Conquer, Recurrence

Exercise (Cont’d):
􏰀 For simplicity, assume n is a power of 2, say n = 2k: 􏰀
= 32 ×T(2k−2)+3×5+5
= 32 ×􏰗3×T(2k−3)+5􏰘+3×5+5
= 33 ×T(2k−3)+32 ×5+3×5+5
= 3k ×T(2k−k)+3k−1 ×5+3k−2 ×5+…+3×5+5
= 3k+5×􏰂􏰁k−13i􏰃 i=0
= 3k+5×􏰂3k−1􏰃 2
= 3.5×3k−2.5
􏰀 So, our guess is: T(n) = 3.5×3logn −2.5 = 3.5×nlog3 −2.5.
3×T(2k−1)+5
= 3×􏰗3×T(2k−2)+5􏰘+5
Topic 4: Divide-and-Conquer, Recurrence

Exercise (Cont’d):
􏰀 Next, prove T(2k) = 3.5 × 3k − 2.5, for k ≥ 0, by induction
􏰀 Basestep: k=0andT(20)=1=3.5−2.5.
􏰀 Inductive step: Assume that T (2k−1 ) = 3.5 × 3k−1 − 2.5. By recurrence relation
T(2k) = 3×T(2k )+5 = 3×T(2k−1)+5, 2
T(2k) = 3× 3.5×3k−1 −2.5 +5 = 3.5×3k −2.5.
Thus, it holds for inductive step too.
􏰀 Therefore, T(2k) = 3.5×3k −2.5 holds for any k ≥ 0.
Topic 4: Divide-and-Conquer, Recurrence

2- Recurrence Tree
􏰀 Another method to solve a recurrence (and analyze the running time of a recursive program)
􏰀 Not as formal as iterated substitution; more visual
􏰀 Consider the Merge-Sort and the tree for the recursive calls of it:
(1,n2) (n2 +1,n)

(1, n) (n +1, n)(n +1, 3n) (3n +1,n) 442244
(1,2) (3,4) …… (n−1,n)

(1,1) (2,2) (3,3) (4,4) (n−1,n−1) (n,n) 􏰀 Question: the number of KC per cell?
Topic 4: Divide-and-Conquer, Recurrence

Merge sort recursion tree (KC per cell):
􏰀 Assuming merge(n) takes ∼ n KC:
(1,n2) (n2 +1,n)

(1, n) (n +1, n) (n +1, 3n) (3n +1,n) 442244
level 1: n
level 2: n
Topic 4: Divide-and-Conquer, Recurrence
level 3: n ……… …
(1,2) (3,4) …… (n−1,n)
(1,1) (2,2) (3,3) (4,4) (n − 1,n − 1) (n,n)
Where k = log n.
total: kn 􏰀 Therefore, the running time of Merge-Sort is (as found before):
Θ(n log n).
􏰀 Note: the recurrence tree method is not as applicable nor as formal as the iterated substitution.
level k: n
level k + 1: 0

3- Guess and Test method:
􏰀 First make a guess for the closed form of the recurrence
􏰀 Guess can come from the iterated substitution, recurrence tree, or previous experiences
􏰀 But regardless of the method, your guess must be verified!
􏰀 Prove the guess by induction
􏰀 May have to change the guess if the inductive proof fails
􏰀 Example: Find a closed form for 􏰎T(n2)+2T(n4)+2n ifn≥4
T (n) = n if 1 ≤ n ≤ 3
􏰀 Solution: We guess that T (n) ∈ Θ(n log n)
􏰀 Need to show that there are constants c, d > 0 and naturals n0 , n1 such that:
(i) T(n) ≤ cnlogn for any n ≥ n0, and (ii) T(n) ≥ dnlogn for any n ≥ n1.
􏰀 We use inductive reasoning to help us find these constants.
Topic 4: Divide-and-Conquer, Recurrence

Topic 4: Divide-and-Conquer, Recurrence
􏰀 (i) Base case: Let’s consider n0 = 4 to see if it can work.
T(4) = T(2)+2T(1)+8 = 2+2+8 = 12 so T(4) ≤ c·4·lg(4) = 8c for c ≥ 12/8 = 3/2.
􏰀 AssumeT(i)≤cilogiforallvaluesofi 1 be constants, let f(n) be a function.
Let T(n) be defined on nonnegative integers by the recurrence
T(n) = aT(nb ) + f(n).
Then T(n) has the following asymptotic bounds:
1. If f(n) ∈ O(nlogb a−ε), for some ε > 0 then T(n) ∈ Θ(nlogb a).
2. Iff(n)∈Θ(nlogbalogkn)forsomek≥0then
T (n) ∈ Θ(nlogb a logk+1 n),
3. If f(n) ∈ Ω(nlogb a+ε) for some constant ε > 0, and if
af(nb ) ≤ δf(n) for some constant δ < 1 and all sufficiently large n, then T(n) ∈ Θ(f(n)). Topic 4: Divide-and-Conquer, Recurrence Some examples: 􏰎 1 if n = 1 1. T(n)= 7T(n2)+n2 if n≥2 a=7,b=2,f(n)=n2 ⇒logba=log27>2.8,sof(n)∈O(nlog7−0.1) and T(n) ∈ Θ(nlog 7)
􏰎 1 if n ≤ 2
2. T(n)= 14T(n3)+n3 if n≥3
a = 14,b = 3,f(n) = n3 ⇒ logb a = log3(14) ∈ (2,3), since f(n)∈Ω(nlog3(14)+ε)forε=3−log3(14),and14􏰗n􏰘3≤14n3 (i.e.with
δ = 2/3 in case 3) T(n) ∈ Θ(n3)
􏰎 1 if n = 1
3.T(n)= 2T(n2)+n ifn≥2
a=2,b=2,f(n)=n,sincenlogba =n=f(n),wehave f(n) ∈ Θ(nlog2 2) and so (by case 2) T(n) ∈ Θ(nlogn).
􏰎 1 if n = 1 4.T(n)= 5T(n2)+n2logn ifn≥2
a=5,b=2,f(n)=n2logn. Sologba=log5>2.3,so f(n) ∈ O(nlog 5−0.1) and T(n) ∈ Θ(nlog 5)
Topic 4: Divide-and-Conquer, Recurrence

Master Theorem doesn’t always apply:
ifn≥2 if n = 1
􏰏4T(n)+ n2 2 log n
Topic 4: Divide-and-Conquer, Recurrence
a = 4, b = 2, logb a = 2
f(n)= n2 ∈/Θ(n2);
f(n)= n2 ∈O(n2)butf(n)= n2 ∈/O(n2−ε)foranyε>0.
log n log n
What can we do to get the closed form? — iterated substitution!

= 4×T(2k−1)+22k
Topic 4: Divide-and-Conquer, Recurrence
= 42 ×T(2k−2)+4× 22(k−1) + 22k
k−1 k = 42×T(2k−2)+22k +22k
= 43 ×T(2k−3)+42 × 22(k−2) + 22k + 22k k−2 k−1 k
= 43×T(2k−3)+22k +22k +22k
k−2 = 4k×T(1)+ 22k
k−1 k +…+22k +22k
= 4k×T(1)+22k􏰗1 +1 +1 +…+1􏰘
= 4k ×T(1)+4k ×H(k)
(Harmonicseries: H(n)=􏰗1+12 +13 +…+n1􏰘=lnn+O(1)=Θ(logn),
CLRS p.1147).
Therefore, T (n) = n2 × T (1) + n2 × H(log n) ∈ Θ(n2H(log n)). Further we have H(k) ∈ Θ(log k) (in fact H(k) = ln k + Θ(1)), thus T(n) ∈ Θ(n2H(logn)) = Θ(n2 loglogn).
k−1 k 123 k

An exercise — dealing with floor & ceiling:
T(n)= T(⌈n2⌉)+1, ifn≥2
􏰀 Examine some small cases: T (1) = 1
T (3) = T (4) = 3
T (5) = T (6) = T (7) = T (8) = 4
Guess: T(n)=k+1,forany2k−1 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com