Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 3 Prof. Erik Demaine Day 4 Introduction to Algorithms L3.2 The divide-and-conquer design paradigm 1. Divide the problem (instance) into subproblems. 2. Conquer the subproblems by solving them recursively. 3. Combine subproblem solutions. Day 4 Introduction to Algorithms L3.3 Example: merge sort 1. Divide: Trivial. 2. Conquer: Recursively sort 2 subarrays. 3. Combine: Linear-time merge. T(n) = 2 T(n/2) + O(n) # subproblems subproblem size work dividing and combining Day 4 Introduction to Algorithms L3.4 Master theorem (reprise) T(n) = aT(n/b) + f (n) CASE 1: f (n) = O(n log b a – ε ) ? T(n) = Θ(n log b a ) . CASE 2: f (n) = Θ(n log b a lg k n) ? T(n) = Θ(n log b a lg k+1 n) . CASE 3: f (n) = ?(n log b a + ε ) and af(n/b) ≤ cf(n) ? T(n) = Θ( f (n)) . Merge sort: a = 2, b = 2 ? n log b a = n ? CASE 2 (k = 0) ? T(n) = Θ(n lg n) . Day 4 Introduction to Algorithms L3.5 Binary search Example: Find 9 357891215 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial. Day 4 Introduction to Algorithms L3.6 Binary search Example: Find 9 357891215 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial. Day 4 Introduction to Algorithms L3.7 Binary search Example: Find 9 357891215 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial. Day 4 Introduction to Algorithms L3.8 Binary search Example: Find 9 357891215 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial. Day 4 Introduction to Algorithms L3.9 Binary search Example: Find 9 357891215 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial. Day 4 Introduction to Algorithms L3.10 Binary search Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial. Example: Find 9 357891215 Day 4 Introduction to Algorithms L3.11 Recurrence for binary search T(n) = 1 T(n/2) + Θ(1) # subproblems subproblem size work dividing and combining n log b a = n log 2 1 = n 0 = 1 ? CASE 2 (k = 0) ? T(n) = Θ(lg n) . Day 4 Introduction to Algorithms L3.12 Powering a number Problem: Compute a n , where n ∈ N. a n = a n/2 ? a n/2 if n is even; a (n–1)/2 ? a (n–1)/2 ?a if n is odd. Divide-and-conquer algorithm: T(n) = T(n/2) + Θ(1) ? T(n) = Θ(lg n) . Naive algorithm: Θ(n). Day 4 Introduction to Algorithms L3.13 Fibonacci numbers Recursive definition: F n = 0 if n = 0; F n–1 + F n–2 if n ≥ 2. 1 if n = 1; 0112358132134L Naive recursive algorithm: ?(φ n ) (exponential time), where φ = is the golden ratio. 2/)51( + Day 4 Introduction to Algorithms L3.14 Computing Fibonacci numbers Naive recursive squaring: F n = φ n / rounded to the nearest integer.5 ? Recursive squaring: Θ(lg n) time. ? This method is unreliable, since floating-point arithmetic is prone to round-off errors. Bottom-up: ? Compute F 0 , F 1 , F 2 , …, F n in order, forming each number by summing the two previous. ? Running time: Θ(n). Day 4 Introduction to Algorithms L3.15 Recursive squaring n FF FF nn nn ? ? ? ? ? ? = ? ? ? ? ? ? ? + 01 11 1 1 Theorem: . Proof of theorem. (Induction on n.) Base (n = 1): . 1 01 11 01 12 ? ? ? ? ? ? = ? ? ? ? ? ? FF FF Algorithm: Recursive squaring. Time = Θ(lg n) . Day 4 Introduction to Algorithms L3.16 Recursive squaring . . Inductive step (n ≥ 2): n n FF FF FF FF nn nn nn nn ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ?? ? ? + 01 11 01 11 1 01 11 01 11 21 1 1 1 Day 4 Introduction to Algorithms L3.17 Matrix multiplication ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? nnnn n n nnnn n n nnnn n n bbb bbb bbb aaa aaa aaa ccc ccc ccc L MOMM L L L MOMM L L L MOMM L L 21 22221 11211 21 22221 11211 21 22221 11211 ∑ = ?= n k kjikij bac 1 Input: A = [a ij ], B = [b ij ]. Output: C = [c ij ] = A?B. i, j = 1, 2,… , n. Day 4 Introduction to Algorithms L3.18 Standard algorithm for i ← 1 to n do for j ← 1 to n do c ij ← 0 for k ← 1 to n do c ij ← c ij + a ik ? b kj Running time = Θ(n 3 ) Day 4 Introduction to Algorithms L3.19 Divide-and-conquer algorithm n×n matrix = 2×2 matrix of (n/2)×(n/2) submatrices: IDEA: ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? hg fe dc ba ut sr C =A ? B r=ae+bg s=af+bh t=ce+dh u=cf+dg 8 mults of (n/2)×(n/2) submatrices 4 adds of (n/2)×(n/2) submatrices Day 4 Introduction to Algorithms L3.20 Analysis of D&C algorithm n log b a = n log 2 8 = n 3 ? CASE 1 ? T(n) = Θ(n 3 ). No better than the ordinary algorithm. # submatrices submatrix size work adding submatrices T(n) = 8 T(n/2) + Θ(n 2 ) Day 4 Introduction to Algorithms L3.21 7 mults, 18 adds/subs. Note: No reliance on commutativity of mult! 7 mults, 18 adds/subs. Note: No reliance on commutativity of mult! Strassen’s idea ? Multiply 2×2 matrices with only 7 recursive mults. P 1 = a ? ( f – h) P 2 = (a + b) ? h P 3 = (c + d) ? e P 4 = d ? (g – e) P 5 = (a + d) ? (e + h) P 6 = (b – d) ? (g + h) P 7 = (a – c) ? (e + f ) r = P 5 + P 4 – P 2 + P 6 s = P 1 + P 2 t = P 3 + P 4 u = P 5 + P 1 – P 3 – P 7 Day 4 Introduction to Algorithms L3.22 Strassen’s idea ? Multiply 2×2 matrices with only 7 recursive mults. P 1 = a ? ( f – h) P 2 = (a + b) ? h P 3 = (c + d) ? e P 4 = d ? (g – e) P 5 = (a + d) ? (e + h) P 6 = (b – d) ? (g + h) P 7 = (a – c) ? (e + f ) r = P 5 + P 4 – P 2 + P 6 =(a + d)(e + h) + d (g – e) – (a + b) h + (b – d)(g + h) = ae + ah + de + dh + dg –de – ah – bh + bg + bh – dg – dh = ae + bg Day 4 Introduction to Algorithms L3.23 Strassen’s algorithm 1. Divide: Partition A and B into (n/2)×(n/2) submatrices. Form terms to be multiplied using + and – . 2. Conquer: Perform 7 multiplications of (n/2)×(n/2) submatrices recursively. 3. Combine: Form C using + and – on (n/2)×(n/2) submatrices. T(n) = 7 T(n/2) + Θ(n 2 ) Day 4 Introduction to Algorithms L3.24 Analysis of Strassen T(n) = 7 T(n/2) + Θ(n 2 ) n log b a = n log 2 7 ≈ n 2.81 ? CASE 1 ? T(n) = Θ(n lg 7 ). Best to date (of theoretical interest only): Θ(n 2.376L ). The number 2.81 may not seem much smaller than 3, but because the difference is in the exponent, the impact on running time is significant. In fact, Strassen’s algorithm beats the ordinary algorithm on today’s machines for n ≥ 30 or so. Day 4 Introduction to Algorithms L3.25 VLSI layout Problem: Embed a complete binary tree with n leaves in a grid using minimal area. H(n) W(n) H(n)= H(n/2) + Θ(1) = Θ(lg n) W(n)= 2W(n/2) + Θ(1) = Θ(n) Area = Θ(n lg n) Day 4 Introduction to Algorithms L3.26 H-tree embedding L(n) L(n) L(n/4) L(n/4)Θ(1) L(n)= 2L(n/4) + Θ(1) = Θ() n Area = Θ(n) Day 4 Introduction to Algorithms L3.27 Conclusion ? Divide and conquer is just one of several powerful techniques for algorithm design. ? Divide-and-conquer algorithms can be analyzed using recurrences and the master method (so practice this math). ? Can lead to more efficient algorithms