Introduction to algorithms 6.046J/18.401J/SMA5503 Lecture 3 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 3 Prof. Erik Demaine
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.2
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
Example: merge sort 1 Divide: trivial 2. Conquer. recursively sort 2 subarrays 3. Combine: Linear-time merge 7(n)=2(m2)+O(m) subproblems work dividing and combining subproblem size Day 4 Introduction to Algorithms L3.3
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
Master theorem(reprise) 7(n)=a(m/b)+f(n) CASE 1: f(n)=O(nlogba-E →(n)=(n0g) CASE 2: f(n)=o(nlogbalgkn →7(n)=( logba Ig+ln) CASE 3: f (n)=92(noga+a)and af(n/b)scf(n) →7(m)=((n) Merge sort: a=2, 6=2= noga=n →CASE2(k=0)→7m)=mnln) Day 4 Introduction to Algorithms
Day 4 Introduction to Algorithms L3.4 Master theorem (reprise) T(n) = a T(n/b) + f(n) CASE 1: f(n) = O(nlogba – ε) ⇒ T(n) = Θ(nlogba) . CASE 2: f(n) = Θ(nlogba lgkn) ⇒ T(n) = Θ(nlogba lgk+1n) . CASE 3: f(n) = Ω(nlogba + ε) and a f(n/b) ≤ c f(n) ⇒ T(n) = Θ(f(n)) . Merge sort: a = 2, b = 2 ⇒ nlogba = n ⇒ CASE 2 (k = 0) ⇒ T(n) = Θ(n lg n)
Binary search Find an element in a sorted array 1 Divide: check middle element 2. Conquer: Recursively search I subarray 3. Combine. trivial Example: find 9 357891215 Day 4 Introduction to Algorithms L3.5
Day 4 Introduction to Algorithms L3.5 Binary search Example: Find 9 3 5 7 8 9 12 15 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial
Binary search Find an element in a sorted array 1 Divide: check middle element 2. Conquer: Recursively search I subarray 3. Combine. trivial Example: find 9 357891215 Day 4 Introduction to Algorithms L36
Day 4 Introduction to Algorithms L3.6 Binary search Example: Find 9 3 5 7 8 9 12 15 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial
Binary search Find an element in a sorted array 1 Divide: check middle element 2. Conquer: Recursively search I subarray 3. Combine. trivial Example: find 9 357891215 Day 4 Introduction to Algorithms L3.7
Day 4 Introduction to Algorithms L3.7 Binary search Example: Find 9 3 5 7 8 9 12 15 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial
Binary search Find an element in a sorted array 1 Divide: check middle element 2. Conquer: Recursively search I subarray 3. Combine. trivial Example: find 9 357891215 Day 4 Introduction to Algorithms L3.8
Day 4 Introduction to Algorithms L3.8 Binary search Example: Find 9 3 5 7 8 9 12 15 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial
Binary search Find an element in a sorted array 1 Divide: check middle element 2. Conquer: Recursively search I subarray 3. Combine. trivial Example: find 9 357891215 Day 4 Introduction to Algorithms
Day 4 Introduction to Algorithms L3.9 Binary search Example: Find 9 3 5 7 8 9 12 15 Find an element in a sorted array: 1. Divide: Check middle element. 2. Conquer: Recursively search 1 subarray. 3. Combine: Trivial
Binary search Find an element in a sorted array 1 Divide: check middle element 2. Conquer: Recursively search I subarray 3. Combine. trivial Example: find 9 357891215 Day 4 Introduction to Algorithms L3.10
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 3 5 7 8 9 12 15