CS代写 EECS 3101 Sums & Recurrences Fact Sheet

STUDY MATERIAL:
• [CLRS] Appendix A, chapter 4
• Lecture Notes 3, 3a

Copyright By PowCoder代写 加微信 powcoder

Summations:
𝑓𝑖 =𝑓1+𝑓2+⋯+𝑓𝑛=Θ(?) 𝑖=1
2𝑖=Θ 𝑛2𝑛 𝑖=1
Recurrence Relations:
𝑇𝑛−1+𝑓(𝑛) ∀𝑛≥1 𝑛 𝑇𝑛=0 ∀𝑛<1⟹𝑇𝑛= 𝑓(𝑖) 𝑇𝑛=2𝑇𝑛−1+1 ∀𝑛≥1⟹𝑇𝑛=Θ2𝑛 0 ∀𝑛 < 1 Summations & Recurrence Relations arise in the running time analysis of algorithms.  SUMMATIONS:  Classic Methods: Arithmetic, Geometric, Harmonic, Bounded Tail  Approximating Summation by Integration  Summation by Parts  ASSUME: ASymptotic SUmmation Made Easy  RECURRENCE RELATIONS:  Iteration method  Recursion tree method  Divide-&-Conquer Recurrence: The Master Method  Guess-&-Verify method  Full History Recurrences  Variable Substitution method f : Ν  R S(n)  f(i)  f(1)f(2) f(3) f(n)  Arithmetic (or polynomial): S(n) = Q(n f(n)) = n(n+1)/2 = Q( n2 ) = n(n+1)(2n+1)/6 = Q( n3 ) = Q( nd+1 ), for any constant real d > -1
f(n) = n: f(n) = n2: f(n) = nd:
1 + 2 + ··· + n 12 + 22 + ··· + n2 1d + 2d + ··· + nd
Classic Methods
S(n) = Q(f(n))
= Q(xn) if x > 1 (Geometric increasing)
f(n) = 2n: 1+ 2 + 22 + ··· + 2n = Q(2n) (with x = 2)  Harmonic: S(n) = Q(log n)
f(n) = 1/n: H(n) = 1 + 1/2 + 1/3 + ··· + 1/n ≈ ln n = Q(log n)
 Bounded Tail: S(n) = Q(1)
1 + x + x2 + ··· + xn = (1 – xn+1)/(1-x) = Q(1) if 02(1/4) = 1⁄2
> 4(1/8) = 1⁄2 > 8(1/16) = 1⁄2
 1 + 1⁄2 log n  W(log n)
 H(n) = Q(log n)

ASSUME : ASymptotic SUmmation Made Easy
f: N  + :
S(n) = f(1) + f(2) + f(3) + ··· + f(n)
max { f(1) , f(2) , … , f(n) } min { f(1) , f(2) , … , f(n) }
average {f(1) , f(2), … , f(n) }
maxn(f) minn(f)
= n · aven(f)
0  minn(f)  aven(f)  maxn(f)
f  minn(f) = f(1) , maxn(f) = f(n) f  minn(f) = f(n) , maxn(f) = f(1)
max{ n · minn(f), maxn(f) }  S(n)  n · maxn(f)
 S(n) = Q( g(n) · maxn(f)) for some 1  g(n)  n
ASSUME: A method for finding g(n) (and hence, S(n)).

f: N  + FACT: f is monotone
(1) f(n) = 0
(2) f(n) = Q(1)
(3) f(n) = w(1)
(4) f(n) = o(1)
S(n) = f(1) + f(2) + f(3) + ··· + f(n)  exactly one of the following holds:
and f and f(1) > 0
ASSUME on monotone f(n)
Cases (1) & (2): g(n) = Q(n), S(n) = Q(g(n) f(n)) = Q(n f(n)) Case (3): Considered next.
Case (4): Similar methods apply. Exercise.

ASSUME for f & f(n) = w(1)
f(m)  cf(n)  f(m+1) 0 −1 𝑖𝑓 𝑒 = −1 𝑖𝑓 𝑒 < −1 𝑛4, 1 23𝑛 𝑛2+log 𝑛 A Simple form The SAFs we encounter, usually have the following simple form: f(n)Qtn nd logen for some real constants t>0, d, e. We classify S(n) for such f(n) as:
Geometric (increasing)
Arithmetic
quasi Harmonic
Bounded tail (polynomially decreasing)
Bounded tail (geometrically decreasing)

RECURRENCE RELATIONS
T (n)  2Tn2  Q(n) O(1)
for n  O(1) for n  O(1)
T (n)  Q(n log n)

The Iteration Method
0 for n0 T(n1)f(n) for n1
The iteration method (or unwinding the recurrence):
T ( n )  
T(n) = f(n) + T(n –1)
= f(n) + f(n-1) + T(n –2)
= f(n) + f(n-1) + f(n-2) + T(n –3)
the driving function of the recurrence
= f(n) + f(n-1) + f(n-2) + ··· + f(3) + f(2) + T(1)
= f(n) + f(n-1) + f(n-2) + ··· + f(3) + f(2) + f(1) + T(0) = f(n) + f(n-1) + f(n-2) + ··· + f(3) + f(2) + f(1).
Example: f(n) = Q(n)  T(n) = Q(n2). f(n) = Q(2n)  T(n) = Q(2n).

The Iteration Method
T ( n )   0
T(n) = n + 2T(n/2)
=n +2[n/2+2T(n/22)]
= 2n + 22 T(n/22)
= 2n + 22 [n/22 + 2 T(n/23)]
= 3n + 23 T(n/23)
= 3n + 23 [n/23 + 2T(n/24)]
f o r n  1 2Tnn forn1
= 4n + 24 T(n/24) =…
=kn+2k T(n/2k) = n(1 + log n) = Q(n log n )
takek=1+logn, T(n/2k)=0

The Iteration Method
T ( n )   0 f o r n  1 2Tnn2 for n1
T(n) = n2 + 2T(n/2)
= n2 + 2 [(n/2)2 + 2T(n/22)]
= n2(1+ 1⁄2) + 22 T(n/22)
= n2(1+ 1⁄2) + 22 [(n/22)2 + 2 T(n/23)]
= n2(1+ 1⁄2 + 1⁄22) + 23 T(n/23)
= n2(1+ 1⁄2 + 1⁄22) + 23 [(n/23)2 + 2T(n/23)]
=n2(1+1⁄2+1⁄22+1⁄23)+24 T(n/24) =…
=n2(1+1⁄2+1⁄22+1⁄23 +···+1⁄2k)+2k+1 T(n/2k+1)
take k = log n, T(n/2k+1) = 0
=n2(1+1⁄2+1⁄22+1⁄23 +···+1⁄2k)
= n2 · Q(1) geometric decreasing = Q(n2 )

The Recursion Tree Method
T ( n )   0 T(n/2)
4f(n/4) 8f(n/8)
f o r n  1 2Tnf(n) forn1
T(n/8) T(n/8)
f(n/8) f(n/8)
T(n/8) T(n/8)
T(n/8) T(n/8)
f(n/8) f(n/8)
T(n) f(n)2f(n2)4f(n4)8f(n8)

T ( n )   0
CLAIM: T(n) = Q(n). Lower bound: T(n)  W(n) obvious
The Recursion Tree Method
f o r n  4 TnTnn forn4
 3n/4  (3/4)2n
T(n/32) T(n/32)
T(n/16) T(n/32)
T(n/16) T(n/16)
n/64 n/32 n/32
T ( n )  n   3 4 n   3 4  n   3 4  n     
Upper bound
n1     4nO(n). 444

The Recursion Tree Method
f o r n  4 TnTnn forn4
T ( n )   0
This is a special case of the following recurrence:
T(n) = T(an) + T(bn) + Q(n)
where 0  a < 1 and 0  b < 1 are real constant parameters. (1) a  b  1  T(n) = Q(n) [linear] (2) a  b  1  T(n) = Q(n log n) (3) a  b  1  T(n) = Q(nd) [super-linear poly] where d > 1 is the unique constant
that satisfies the equation ad + bd = 1.
[See the guess-&-verify method later & Exercise 9.]

Divide-&-Conquer
MergeSort is the prototypical divide-&-conquer algorithm. Here is a high level description:
Algorithm MergeSort( S ) § John von Neumann [1945] Pre-Condition: input S is a sequence of numbers
Post-Condition: output is a sorted permutation of the input sequence
Base: Divide: Conquer: Combine: Output: end
if |S|  1 then return S
Divide S into its left and right halves S=L, R, |L||R| 1⁄2|S| L’  MergeSort( L ); R’  MergeSort( R )
S’  Merge( L’, R’ ) return S’

MergeSort Example
23 15 41 82 37 92 66 31 34 73 25 19 33 15 16 58
66 34 73 19
15 16 33 58
23 31 37 41 66 82 92
25 33 34 58 73
15 15 16 19 23 25 31 33 34 37 41 58 66 73 82 92

Algorithm MergeSort(A[1..n]) B[0..n+1]  auxiliary array for merging MS(1,n)
procedure MS( s, f ) § sort A[s..f]
MERGE Loop Invariant:
s-1 i m-1m j f+1 B
if s  f then return m  (s+f)/2
Combine: Merge( s, m, f ) end
merged so far
MS( s, m –1 ) ; MS( m, f )
right half
procedure Merge( s, m, f ) B[s-1 .. m-2]  A[s,m-1]
B[m .. f]  A[m,f]
B[m-1] B[f+1] § barrier sentinel i  s-1 ; j  m
for k  s .. f do if B[i]  B[j]
Merge time = Q(n), where n = f – s +1.
then A[k]  B[i]; i++ else A[k]  B[j]; j++

MergeSort Recurrence: T(n)=Q(1) n1
T(n) = T( n/2 ) + T( n/2 ) + Q(n) n>1 Simplified Recurrence:
if s  f then return m  (s+f)/2
Algorithm MergeSort(A[1..n]) B[0..n+1]  auxiliary array for merging MS(1,n)
procedure MS( s, f ) § sort A[s..f]
Combine: Merge( s, m, f ) end
MS( s, m –1 ) ; MS( m, f )
T(n) = 2 T(n/2) + Q(n) T(n) = Q(1)
for n > 1 forn1
procedure Merge( s, m, f ) B[s-1 .. m-2]  A[s,m-1]
B[m .. f]  A[m,f]
B[m-1] B[f+1] § barrier sentinel i  s-1 ; j  m
for k  s .. f do if B[i]  B[j]
then A[k]  B[i]; i++ else A[k]  B[j]; j++
T(n) = Q( n log n).

Divide-&-Conquer Recurrence
𝑎𝑇𝑛𝑏 +𝑓(𝑛) ∀𝑛>1 Θ 1 ∀𝑛 ≤ 1
a = # of recursive calls (a > 0)
n/b = size of each sub-instance called recursively (b > 1) f(n) = cost of divide + combine steps
(every thing except the recursive calls).
In MergeSort we have:
a = 2 recursive calls
of size n/b = n/2 each.
Cost of divide = Q(1)
Cost of Combine, i.e., merge, is Q(n). So, f(n) = Q(n).

T ( n )   a T ( bn )  f ( n )  n  1 Q(1) n1
Recursion Tree:
f(n/b) f(n/b) f(n/b)
f(n/b2) f(n/b2) f(n/b2) f(n/b2)
k = logbn
f(n) af(n/b) a2f(n/b2)
ak-1f(n/bk-1) h(n) = Q(n logba )
f(n/bk-1) f(n/bk-1)
a logb n = n logb a
(compare their logarithms)
h(n) = ak ·Q(1) = Q(ak) = Q(alogbn ) = Qalogbn) = Qnlogba)
k = logbn = Q( log n). 36

T(n)aT(bn)f(n) n1 Q(1) n  1
T(n) = S(n) + h(n) = Q( max{S(n), h(n)}) h(n) = Q n logba )
S(n)= S f(n)af(n)a2f(n)ak1fn 
S ( n )  k  1 a i f  n 
a logb n = n logb a (compare their logarithms)
h(n) = ak ·Q(1) = Q(ak) = Q(alogbn ) = Qalogbn) = Qnlogba)
k = logbn = Q( log n). 37
ak-1f(n/bk-1)
h(n) = Q(n logba )

T(n)aT(bn)f(n) n1 Q(1) n1
T(n) = S(n) + h(n) Special Solution: contribution of the internal nodes of the recursion tree.
Homogeneous Solution: contribution of the leaves of the recursion tree.
h(n)ah(bn) n1 h(n)=Qnlogba) Q(1) n1
T(n) = h(n)( Q(n) + 1 )
Define: Q(n)S(n), r(n) f(n) h(n) h(n)
Q(n)r(n)rbnrn rn  b2 b3
Q(n)Q(bn)r(n) n1  0  n  1
f(n) is a SAF  r(n) is a SAF

Q(n) S(n), r(n) f(n) h(n) h(n)
T(n) = h(n)( Q(n) + 1 )
f(n) is a SAF  r(n) is a SAF
↪ Let n=bk forintegerk=Q(logn).
k Q(n)  Qrbi 
Q(n)=Q( ? )
T(n)=Q( ? )
Q(loge n) e > -1
f(n)log n
Q(log-1 n)
h(n)log log n
O(loge n) e < -1 T ( n )   a T ( bn )  f ( n )  n  1 Q(1) n1 h(n) = Q n logba ) THE MASTER THEOREM Suppose f(n) is a SAF, and e  0 & e are constant reals. 𝒇(𝒏) / 𝒉(𝒏) Compare with CLRS. See Exercise 4. 𝚯 𝐥𝐨𝐠𝒆𝒏 (e > -1)
𝚯 𝐥𝐨𝐠𝒆𝒏 (e = -1)
𝐎 𝐥𝐨𝐠𝒆𝒏 (e < -1) f(n) » h(n) f(n) « h(n) 𝛩(𝑓(𝑛)log𝑛) = 𝛩(𝑛log𝑏𝑎log𝑒+1𝑛) 𝛩(h(𝑛) log log 𝑛) = 𝛩(𝑛log𝑏𝑎 log log 𝑛) 𝛩(h(𝑛)) = 𝛩(𝑛log𝑏𝑎) T ( n )   a T ( bn )  f ( n )  n  1 Q(1) n1 h(n) = Q n logba ) f(n) = Q( tn nd log e n) constants t > 0, d, e.
T(n) = Q(f(n))
T(n) = Q(f(n))
d = logb a
T(n) = Q(f(n) log n)
T(n) = Q(h(n) log log n)
T(n) = Q(h(n))
T(n) = Q(h(n))
T(n) = Q(h(n))

EECS 3101 Sums & Recurrences Fact Sheet
log 𝑥𝑦 = log 𝑥 + log 𝑦
log𝑥𝑦 =𝑦log𝑥
log𝑦 𝑥 = log 𝑥 / log 𝑦 log(1±𝑥)=±Θ(𝑥) for𝑥=𝑜(1)
Θ 𝑛𝑑+1 if d > −1 Θ(log𝑛) ifd=−1 Θ 1 if d < −1 𝑥𝑛+1−1 if0≠|𝑥|≠1 𝑥−1 Θ 𝑥𝑛 if x > 1
Θ 1 if 0 < x < 1 Forf↑: 𝑓𝑥𝑑𝑥≤ 𝑚−1 𝑓𝑖 ≤ 𝑓𝑥𝑑𝑥 𝑚 For f ↓: 𝑓 𝑥 𝑑𝑥 ≥ 𝑚−1 𝑓 𝑖 ≥ 𝑓 𝑥 𝑑𝑥 𝑚 ASSUME[ASymptotic SUmmationMade Easy] g(n)← 𝑛−𝑚 where log𝑓 𝑚 =log𝑓 𝑛 −Θ 1 : 𝑆𝑛 = 𝑛𝑖=1𝑓𝑖 𝑓𝑜𝑟𝑓𝑛 ↑=𝜔1 𝐟↑𝐚𝐧𝐝𝐠↑ ⇒ 𝐒𝐧 =𝚯 𝐠𝐧 𝐟𝐧 . 𝒇(𝒏) : 𝒂 𝑺𝑨𝑭 𝑺𝒏= 𝒇(𝒊) 𝒊=𝟏 Arithmetic 𝜣( 𝒏 𝒇 𝒏 ) Θ(𝑛−1 log𝑒𝑛) , e = a real constant 𝜣 𝐥𝐨𝐠𝒆+𝟏𝒏 𝚯 𝐥𝐨𝐠 𝐥𝐨𝐠 𝒏 𝚯 𝟏 𝒊𝒇 𝒆 > −𝟏 𝒊𝒇 𝒆 = −𝟏 𝒊𝒇 𝒆 < −𝟏 Bounded Tail 𝑛−Ω 1 −1 𝑜𝑟𝑒𝑣𝑒𝑛 𝑂 𝑛−1log𝑒𝑛 , 𝑒<−1 MASTERMETHOD: 𝑻(𝒏) = 𝒂𝑻 𝒏𝒃 +𝒇(𝒏) ∀𝒏>𝟏 , h(𝑛) = Θ 𝑛log𝑏𝑎 , 𝒇 𝒏 ∶ 𝐚𝐒𝑨𝑭, constants 𝜀>0 & 𝑒. 𝜣(𝟏) ∀𝒏 ≤ 𝟏
𝒇 𝒏 ∶ 𝒉(𝒏)
𝒇 𝒏 ≈ 𝒉(𝒏)
Θ(log𝑒𝑛) , 𝑒 >−1
Θ log−1𝑛 , 𝑒 = −1
𝜣(𝒇 𝒏 𝐥𝐨𝐠𝒏)
𝜣(𝒉 𝒏 𝐥𝐨𝐠𝐥𝐨𝐠𝒏)
𝒇 𝒏 ≪ 𝒉(𝒏)
𝑂 𝑛−𝜀 𝑜𝑟𝑒𝑣𝑒𝑛 𝑂(log𝑒𝑛), 𝑒<−1 T ( n )   a T ( bn )  f ( n )  n  1 Q(1) n1 h(n) = Q n logba ) Example 1: Assume a = 2, b = 4, f(n) = Q(nd log2 n). Express T(n) based on the constant parameter d. logb a = log4 2 = 1⁄2  h(n) = Q( 𝑛) d > 1⁄2  T(n) = Q(f(n)) = Q(𝑛𝑑 𝑙𝑜𝑔2𝑛) d = 1⁄2  T(n) = Q(f(n) log n) = Q( 𝑛 𝑙𝑜𝑔3 𝑛) d <1⁄2  T(n)=Q(h(n)) = Q( 𝑛) T ( n )   a T ( bn )  f ( n )  n  1 Q(1) n1 h(n) = Q n logba ) Example 2: Assume b = 3, f(n) = Q(n4 / log n). Express T(n) based on the constant parameter a. h(n)=Q(nlog3a) , bd =34 =81 a < 81  T(n) = Q(f(n)) = Q(n4 / log n) a = 81  T(n) = Q(h(n) log log n) = Q(n4 log log n) a > 81  T(n) = Q(h(n)) = Q(nlog3a)

Guess-&-Verify
BASIC INGRIDIANTS:
 Guess a solution to the recurrence.
 Verify it by mathematical induction.
The induction variable must be a natural number.
E.g., height of the recursion tree (max recursion depth), or
size of the recursion tree (# times you apply the recurrence). n may also be a candidate if it “stays” integer.
 If you spot a place where the verification does not go through, examine it to help revise your guess, and try again.
 One key guiding principle, taken with a grain of salt, is to first make sure the leading term (with its constant coefficient) matches on the LHS and RHS of the recurrence. That will show you to guess higher or lower the next time! After figuring out the leading term, you can apply the same principle to find the lower order terms.

Guess-&-Verify: Example 1
4𝑇𝑛2+𝑛2 𝑓𝑜𝑟𝑛>1 1 𝑓𝑜𝑟 𝑛 ≤ 1
•Clearly𝑇𝑛=Ω𝑛2. Is 𝑇𝑛=𝑂𝑛2? • Guess#1: 𝑇𝑛 =𝑐𝑛2+𝐿𝑛
const. 𝑐 > 0, 𝐿 𝑛 = 𝑜 𝑛2 lower order terms (to be determined) • Plug this guess in the recurrence and verify: 𝑇 𝑛 ? =? 4𝑇 𝑛2 + 𝑛2
𝑐𝑛2+𝐿𝑛 ?=? 4 𝑐 𝑛 2+𝐿 𝑛 +𝑛2 = (𝑐+1)𝑛2+4𝐿 𝑛 222
• LHS leading term < RHS leading term  guess is too low. Guess-&-Verify: Example 1 • Guess#2: 𝑇𝑛 =𝑐𝑛2+𝜀+𝐿𝑛 4𝑇𝑛2+𝑛2 𝑓𝑜𝑟𝑛>1 1 𝑓𝑜𝑟 𝑛 ≤ 1
const. 𝑐 > 0, 𝜀 > 0, 𝐿 𝑛 lower order terms (to be determined) • Plug this guess in the recurrence and verify: 𝑇 𝑛 ? =? 4𝑇 𝑛2 + 𝑛2
𝑐𝑛2+𝜀+𝐿𝑛 ?=? 4 𝑐 𝑛 2+𝜀+𝐿 𝑛 +𝑛2 = 1 𝑐𝑛2+𝜀+4𝐿 𝑛 +𝑛2 2 2 2𝜀 2
• LHS leading term > RHS leading term  guess is too high.

Guess-&-Verify: Example 1
4𝑇𝑛2+𝑛2 𝑓𝑜𝑟𝑛>1 1 𝑓𝑜𝑟 𝑛 ≤ 1
• Guess#3: 𝑇 𝑛 =𝑐𝑛2log𝑛+𝐿 𝑛
const. 𝑐 > 0, 𝐿 𝑛 lower order terms (to be determined) • Plug this guess in the recurrence and verify: 𝑇 𝑛 ? =? 4𝑇 𝑛2 + 𝑛2
𝑐𝑛2log𝑛+𝐿𝑛 ?=? 4 𝑐 𝑛 2log𝑛+𝐿 𝑛 +𝑛2 222
=𝑐𝑛2log𝑛+4𝐿𝑛2 +(1−𝑐)𝑛2
• LHS leading term = RHS leading term  correct guess of high order term.
• Solve the residual recurrence for 𝐿(𝑛) (with revised boundary condition):
𝐿 𝑛 = 4 𝐿 𝑛2 + ( 1 − 𝑐 ) 𝑛 2
Claim: 𝑐 = 1. Why? If 1 − 𝑐 > 0, then 𝐿(𝑛) is not lower order.
If 1 − 𝑐 < 0, then 𝐿(𝑛) becomes negative but the leading term gets larger. Residual recurrence: 𝐿 𝑛 = 4𝐿 𝑛2 (plus revised boundary condition) Solution: L 𝑛 =𝑂 𝑛2 and 𝑇 𝑛 =𝑛2log𝑛+𝑂 𝑛2 =Θ(𝑛2log𝑛). 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com