Divide and Conquer algorithm ppt

divide and conquer examples ppt and divide and conquer algorithm binary search ppt
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
DIVIDE AND CONQUER II master theorem ‣ integer multiplication ‣ matrix multiplication ‣ convolution and FFT ‣ Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne http://www.cs.princeton.edu/wayne/kleinberg-tardos Last updated on Jul 20, 2015, 3:31 PMDIVIDE AND CONQUER II master theorem ‣ integer multiplication ‣ matrix multiplication ‣ convolution and FFT ‣ SECTIONS 4.3-4.6Master method Goal. Recipe for solving common divide-and-conquer recurrences: n T(n)=aT + f(n) b Terms. a ≥ 1 is the number of subproblems. b 0 is the factor by which the subproblem size decreases. f (n) = work to divide/merge subproblems. Recursion tree. k = log n levels. b i a = number of subproblems at level i. i n / b = size of subproblem at level i. 3Case 1: total cost dominated by cost of leaves lg 3 Ex 1. If T (n) satisfies T (n) = 3 T (n / 2) + n, with T (1) = 1, then T (n) = Θ(n ). T (n) n T (n / 2) T (n / 2) T (n / 2) 3 (n / 2) 2 2 T (n / 4) T (n / 4) T (n / 4) T (n / 4) T (n / 4) T (n / 4) T (n / 4) T (n / 4) T (n / 4) 3 (n / 2 ) i i 3 (n / 2 ) log n 2 ⋮ ⋮ ... log n log n 2 2 T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) 3 (n/2 ) log n log 3 2 2 3 =n 1+log n 2 r 1 2 3 log n log 3 2 2 T(n)=(1+r+r +r +...+r ) n r = 3 / 2 1 = =3n 2n n r 1 4Case 2: total cost evenly distributed among levels Ex 2. If T (n) satisfies T (n) = 2 T (n / 2) + n, with T (1) = 1, then T (n) = Θ(n log n). T (n) n 2 (n / 2) T (n / 2) T (n / 2) 2 2 T (n / 4) T (n / 4) 2 (n / 2 ) T (n / 4) T (n / 4) log n 2 3 3 T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) T (n / 8) 2 (n / 2 ) ⋮ ⋮ ... T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) n (1) log n 2 2 =n 2 3 log n 2 r = 1 T(n)=(1+r+r +r +...+r ) n = n (log n + 1) 2 5Case 3: total cost dominated by cost of root 5 5 Ex 3. If T (n) satisfies T (n) = 3 T (n / 4) + n , with T (1) = 1, then T (n) = Θ(n ). T (n) 5 n 5 T (n / 4) T (n / 4) T (n / 4) 3 (n / 4) 2 2 5 T (n / 16) T (n / 16) T (n / 16) T (n / 16) T (n / 16) T (n / 16) T (n / 16) T (n / 16) T (n / 16) 3 (n / 4 ) i i 5 log n 3 (n / 4 ) 4 ⋮ ⋮ ... log n log n 5 4 4 T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) 3 (n/4 ) log n log 3 4 4 3 = n 1 5 5 5 2 3 5 r = 3 / 4 1 n ≤ T (n) ≤ (1 + r + r + r + … ) n ≤ n 1 – r 6Master theorem Master theorem. Suppose that T (n) is a function on the nonnegative integers that satisfies the recurrence n T(n)=aT + f(n) b where n / b means either ⎣ n / b⎦ or ⎡ n / b⎤. Let k = log a. Then, b k – ε k Case 1. If f (n) = O(n ) for some constant ε 0, then T (n) = Θ(n ). Ex. T (n) = 3 T(n / 2) + n. a = 3, b = 2, f (n) = n, k = log 3. 2 lg 3 T (n) = Θ(n ). 7Master theorem Master theorem. Suppose that T (n) is a function on the nonnegative integers that satisfies the recurrence n T(n)=aT + f(n) b where n / b means either ⎣ n / b⎦ or ⎡ n / b⎤. Let k = log a. Then, b k p k p+1 Case 2. If f (n) = Θ(n log n), then T (n) = Θ(n log n). Ex. T (n) = 2 T(n / 2) + Θ(n log n). a = 2, b = 2, f (n) = 17 n, k = log 2 = 1, p = 1. 2 2 T (n) = Θ(n log n). 8Master theorem Master theorem. Suppose that T (n) is a function on the nonnegative integers that satisfies the recurrence n T(n)=aT + f(n) b regularity condition holds k + ε where n / b means either ⎣ n / b⎦ or ⎡ n / b⎤. Let k = log a. Then, if f(n) = Θ(n ) b k + ε Case 3. If f (n) = Ω(n ) for some constant ε 0 and if a f (n / b) ≤ c f (n) for some constant c 1 and all sufficiently large n, then T (n) = Θ ( f (n) ). 5 Ex. T (n) = 3 T(n / 4) + n . 5 a = 3, b = 4, f (n) = n , k = log 3. 4 5 T (n) = Θ(n ). 9Master theorem Master theorem. Suppose that T (n) is a function on the nonnegative integers that satisfies the recurrence n T(n)=aT + f(n) b where n / b means either ⎣ n / b⎦ or ⎡ n / b⎤. Let k = log a. Then, b k – ε k Case 1. If f (n) = O(n ) for some constant ε 0, then T (n) = Θ(n ). k p k p+1 Case 2. If f (n) = Θ(n log n), then T (n) = Θ(n log n). k + ε Case 3. If f (n) = Ω(n ) for some constant ε 0 and if a f (n / b) ≤ c f (n) for some constant c 1 and all sufficiently large n, then T (n) = Θ ( f (n) ). Pf sketch. Use recursion tree to sum up terms (assuming n is an exact power of b). Three cases for geometric series. Deal with floors and ceilings. 10Akra-Bazzi theorem Desiderata. Generalizes master theorem to divide-and-conquer algorithms where subproblems have substantially different sizes. Theorem. Akra-Bazzi Given constants a 0 and 0 b ≤ 1, functions i i 2 c h (n) = O(n / log n) and g(n) = O(n ), if the function T(n) satisfies the recurrence: i k T(n)= a T (b n+h (n))+g(n) i i i i=1 a subproblems small perturbation to handle i floors and ceilings of size b n i k n g(u) p p a b =1 i Then T(n) = where p satisfies . n 1+ du i p+1 u 1 i=1 2 Ex. T(n) = 7/4 T(⎣n / 2⎦) + T(⎡3/4 n⎤) + n . a = 7/4, b = 1/2, a = 1, b = 3/4 ⇒ p = 2. 1 1 2 2 h (n) = ⎣1/2 n⎦ – 1/2 n, h (n) = ⎡3/4 n⎤ – 3/4 n. 1 2 2 2 g(n) = n ⇒ T(n) = Θ(n log n). 11DIVIDE AND CONQUER II master theorem ‣ integer multiplication ‣ matrix multiplication ‣ convolution and FFT ‣ SECTION 5.5Integer addition Addition. Given two n-bit integers a and b, compute a + b. Subtraction. Given two n-bit integers a and b, compute a – b. Grade-school algorithm. Θ(n) bit operations. 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 + 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 Remark. Grade-school addition and subtraction algorithms are asymptotically optimal. 13Integer multiplication Multiplication. Given two n-bit integers a and b, compute a × b. 2 Grade-school algorithm. Θ(n ) bit operations. 1 1 0 1 0 1 0 1 × 0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 Conjecture. Kolmogorov 1952 Grade-school algorithm is optimal. Theorem. Karatsuba 1960 Conjecture is wrong. 14Divide-and-conquer multiplication To multiply two n-bit integers x and y: Divide x and y into low- and high-order bits. Multiply four ½n-bit integers, recursively. Add and shift to obtain result. m = ⎡ n / 2 ⎤ m m a = ⎣ x / 2 ⎦ b = x mod 2 use bit shifting to compute 4 terms m m c = ⎣ y / 2 ⎦ d = y mod 2 m m 2m m (2 a + b) (2 c + d) = 2 ac + 2 (bc + ad) + bd 2 3 4 1 Ex. x = 10001101 y = 111 0 0 0 0 1 a b c d 15Divide-and-conquer multiplication MULTIPLY(x, y, n) _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ IF (n = 1) RETURN x 𐄂 y. ELSE m← ⎡ n / 2 ⎤. m m a ← ⎣ x / 2 ⎦; b ← x mod 2 . m m c ← ⎣ y / 2 ⎦; d ← y mod 2 . e ← MULTIPLY(a, c, m). f ← MULTIPLY(b, d, m). g ← MULTIPLY(b, c, m). h ← MULTIPLY(a, d, m). 2m m RETURN 2 e + 2 (g + h) + f. _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 16Divide-and-conquer multiplication analysis Proposition. The divide-and-conquer multiplication algorithm requires 2 Θ(n ) bit operations to multiply two n-bit integers. Pf. Apply case 1 of the master theorem to the recurrence: 2 T(n) = 4T n /2 + Θ(n) ⇒ T(n) =Θ(n ) ( ) " " add, shift recursive calls € 17Karatsuba trick To compute middle term bc + ad, use identity: bc + ad = ac + bd – (a – b) (c – d) m = ⎡ n / 2 ⎤ m m a = ⎣ x / 2 ⎦ b = x mod 2 middle term m m c = ⎣ y / 2 ⎦ d = y mod 2 m m 2m m (2 a + b) (2 c + d) = 2 ac + 2 (bc + ad ) + bd 2m m = 2 ac + 2 (ac + bd – (a – b)(c – d)) + bd 1 1 3 2 3 Bottom line. Only three multiplication of n / 2-bit integers. 18Karatsuba multiplication KARATSUBA-MULTIPLY(x, y, n) _______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ IF (n = 1) RETURN x 𐄂 y. ELSE m ← ⎡ n / 2 ⎤. m m a ← ⎣ x / 2 ⎦; b ← x mod 2 . m m c ← ⎣ y / 2 ⎦; d ← y mod 2 . e ← KARATSUBA-MULTIPLY(a, c, m). f ← KARATSUBA-MULTIPLY(b, d, m). g ← KARATSUBA-MULTIPLY(a – b, c – d, m). 2m m RETURN 2 e + 2 (e + f – g) + f. _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ 19Karatsuba analysis 1.585 Proposition. Karatsuba's algorithm requires O(n ) bit operations to multiply two n-bit integers. Pf. Apply case 1 of the master theorem to the recurrence: lg 3 1.585 T(n) = 3 T(n / 2) + Θ(n) ⇒ T(n) = Θ(n ) = O(n ). Practice. Faster than grade-school algorithm for about 320-640 bits. 20