Introduction to Algorithms6.046J/18.401JThe divide-and-conquer design paradigmMerge sortMerge sortMaster theorem (reprise)Master theorem (reprise)Binary searchBinary searchBinary searchBinary searchBinary searchBinary searchBinary searchRecurrence for binary searchRecurrence for binary searchPowering a numberPowering a numberPowering a numberFibonacci numbersFibonacci numbersComputing Fibonacci numbersComputing Fibonacci numbersRecursive squaringRecursive squaringRecursive squaringRecursive squaringMatrix multiplicationStandard algorithmStandard algorithmDivide-and-conquer algorithmDivide-and-conquer algorithmAnalysis of D&C algorithmAnalysis of D&C algorithmAnalysis of D&C algorithmStrassen’s ideaStrassen’s ideaStrassen’s ideaStrassen’s ideaStrassen’s ideaStrassen’s algorithmStrassen’s algorithmAnalysis of StrassenAnalysis of StrassenAnalysis of StrassenAnalysis of StrassenVLSI layoutVLSI layoutVLSI layoutVLSI layoutVLSI layoutH-tree embeddingH-tree embeddingH-tree embeddingConclusionSeptember 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.1Introduction to Algorithms6.046J/18.401JLECTURE 3Divide and Conquer• Binary search• Powering a number• Fibonacci numbers• Matrix multiplication• Strassen’s algorithm• VLSI tree layoutProf. Erik D. DemaineSeptember 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.2The divide-and-conquer design paradigm1. Divide the problem (instance) into subproblems.2. Conquer the subproblems by solving them recursively.3. Combine subproblem solutions.September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.3Merge sort1. Divide: Trivial.2. Conquer: Recursively sort 2 subarrays.3. Combine: Linear-time merge.September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.4Merge sort1. Divide: Trivial.2. Conquer: Recursively sort 2 subarrays.3. Combine: Linear-time merge.T(n) = 2 T(n/2) + Θ(n)# subproblemssubproblem sizework dividing and combiningSeptember 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.5Master theorem (reprise)T(n) = aT(n/b) + f (n)CASE 1: f (n) = O(nlogba – ε), constant ε > 0⇒ T(n) = Θ(nlogba) .CASE 2: f (n) = Θ(nlogbalgkn), constant k ≥ 0⇒ T(n) = Θ(nlogbalgk+1n) .CASE 3: f (n) = Ω(nlogba + ε ), constant ε > 0, and regularity condition⇒ T(n) = Θ( f (n)) .September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.6Master theorem (reprise)T(n) = aT(n/b) + f (n)CASE 1: f (n) = O(nlogba – ε), constant ε > 0⇒ T(n) = Θ(nlogba) .CASE 2: f (n) = Θ(nlogbalgkn), constant k ≥ 0⇒ T(n) = Θ(nlogbalgk+1n) .CASE 3: f (n) = Ω(nlogba + ε ), constant ε > 0, and regularity condition⇒ T(n) = Θ( f (n)) .Merge sort: a = 2, b = 2 ⇒ nlogba= nlog22= n⇒ CASE 2 (k = 0) ⇒ T(n) = Θ(n lg n) .September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.7Binary searchFind an element in a sorted array:1. Divide: Check middle element.2. Conquer: Recursively search 1 subarray.3. Combine: Trivial.September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.8Binary searchFind an element in a sorted array:1. Divide: Check middle element.2. Conquer: Recursively search 1 subarray.3. Combine: Trivial.Example: Find 9357891215September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.9Binary searchFind an element in a sorted array:1. Divide: Check middle element.2. Conquer: Recursively search 1 subarray.3. Combine: Trivial.Example: Find 9357891215September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.10Binary searchFind an element in a sorted array:1. Divide: Check middle element.2. Conquer: Recursively search 1 subarray.3. Combine: Trivial.Example: Find 9357891215September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.11Binary searchFind an element in a sorted array:1. Divide: Check middle element.2. Conquer: Recursively search 1 subarray.3. Combine: Trivial.Example: Find 9357891215September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.12Binary searchFind an element in a sorted array:1. Divide: Check middle element.2. Conquer: Recursively search 1 subarray.3. Combine: Trivial.Example: Find 9357891215September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.13Binary searchFind an element in a sorted array:1. Divide: Check middle element.2. Conquer: Recursively search 1 subarray.3. Combine: Trivial.Example: Find 9357891215September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.14Recurrence for binary searchT(n) = 1 T(n/2) + Θ(1)# subproblemssubproblem sizework dividing and combiningSeptember 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.15Recurrence for binary searchT(n) = 1 T(n/2) + Θ(1)# subproblemssubproblem sizework dividing and combiningnlogba= nlog21= n0= 1 ⇒ CASE 2 (k = 0)⇒ T(n) = Θ(lg n) .September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.16Powering a numberProblem: Compute an, where n ∈ N.Naive algorithm: Θ(n).September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.17Powering a numberProblem: Compute an, where n ∈ N.Naive algorithm: Θ(n).an=an/2 ⋅ an/2 if n is even;a(n–1)/2 ⋅ a(n–1)/2 ⋅ a if n is odd.Divide-and-conquer algorithm:September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.18Powering a numberProblem: Compute an, where n ∈ N.Naive algorithm: Θ(n).an=an/2 ⋅ an/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) .September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.19Fibonacci numbersRecursive definition:Fn=0 if n = 0;Fn–1+ Fn–2if n ≥ 2.1 if n = 1;0112358132134LSeptember 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.20Fibonacci numbersRecursive definition:Fn=0 if n = 0;Fn–1+ Fn–2if n ≥ 2.1 if n = 1;0112358132134LNaive recursive algorithm: Ω(φn)(exponential time), where φ=is the golden ratio.2/)51(+September 14, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.21Computing Fibonacci numbersBottom-up: • Compute F0, F1, F2, …, Fnin order, forming each number by summing the two previous.• Running time: Θ(n).September 14, 2005 Copyright ©