L6 - Divide-and-Conquer.pdf

CP312 Algorithm Design and Analysis I LECTURE 6: DIVIDE-AND-CONQUER 1 Divide-and-Conquer Algorithms 1. Divide the problem (instance) into subproblems 2. Conquer the subproblems by solving them recursively 3. Combine subproblem solutions 𝑇 𝑛 = 𝑎𝑇 𝑠 𝑛 Running time on input size 𝑛 # of subproblems + 𝐶(...

CP312 Algorithm Design and Analysis I LECTURE 6: DIVIDE-AND-CONQUER 1 Divide-and-Conquer Algorithms 1. Divide the problem (instance) into subproblems 2. Conquer the subproblems by solving them recursively 3. Combine subproblem solutions 𝑇 𝑛 = 𝑎𝑇 𝑠 𝑛 Running time on input size 𝑛 # of subproblems + 𝐶(𝑛) + 𝐷(𝑛) Subproblem size Work dividing Work combining 2 Example: Merge Sort 𝑛 2 𝑛/2 1 Divide 𝑛/2 2 Conquer: Recursively call Merge Sort Conquer: Recursively call Merge Sort 3 Combine Example: Merge Sort Divide: Split the array into 2 sub-arrays Conquer: Recursively sort the 2 sub-arrays Combine: Merge the two sorted sub-arrays 𝑇 𝑛 = 2𝑇 𝑛/2 + Θ 𝑛 + Θ(1) Running time of merge sort on input size 𝑛 # of subproblems Subproblem size Work dividing Work combining 4 Master Theorem (Review) 𝑇 𝑛 = 𝑎𝑇 𝑛/𝑏 + 𝑓(𝑛) Case 1: 𝑓 𝑛 = 𝑂 𝑛log𝑏 𝑎−𝜖 ⇒ 𝑻 𝒏 = 𝚯 𝒏𝐥𝐨𝐠 𝒃 𝒂 Case 2: 𝑓 𝑛 = Θ 𝑛log𝑏 𝑎 lg 𝑘 𝑛 ⇒ 𝑻 𝒏 = 𝚯 𝒏𝒍𝒐𝒈𝒃 𝒂 𝐥𝐠 𝒌+𝟏 𝒏 Case 3: 𝑓 𝑛 = Ω 𝑛log𝑏 𝑎+𝜖 and 𝑎𝑓 𝑛/𝑏 ≤ 𝑐𝑓 𝑛 ⇒ 𝑻 𝒏 = 𝚯 𝒇(𝒏) Where 𝜖 > 0, 𝑘 ≥ 0 5 Case 2: 𝑓 𝑛 = Θ 𝑛log𝑏 𝑎 lg 𝑘 𝑛 ⇒ 𝑻 𝒏 = 𝚯 𝒏𝒍𝒐𝒈𝒃 𝒂 𝐥𝐠 𝒌+𝟏 𝒏 Merge Sort Solving 𝑇 𝑛 = 2𝑇 𝑛/2 + Θ(𝑛) using Master Theorem: 𝑎 = 2, 𝑏 = 2 ⇒ 𝑛log𝑏 𝑎 = 𝑛 Case 2 (𝑘 = 0): 𝑇 𝑛 = Θ(𝑛 lg 𝑛) 6 Binary Search Problem: Find an element in a sorted array. Input: Sorted array 𝐴[1, … , 𝑛] and target element 𝑥 Output: Location of 𝑥 if it exists in 𝐴 or −1 otherwise. 3 5 7 8 12 14 15 7 Binary Search (Find 𝑥 = 7) Divide: Check the middle element Conquer: Recursively search 1 sub-array Combine: Do nothing 3 5 7 8 12 14 15 8 Binary Search (Find 𝑥 = 7) Divide: Check the middle element Conquer: Recursively search 1 sub-array Combine: Do nothing 3 5 7 8 12 14 15 9 Binary Search (Find 𝑥 = 7) Divide: Check the middle element Conquer: Recursively search 1 sub-array Combine: Do nothing 3 5 7 8 12 14 15 10 Recurrence for Binary Search 𝑇 𝑛 = 1𝑇 𝑛/2 + Θ 1 + Θ(1) # of subproblems Subproblem size Work dividing Work combining 𝑎 = 1, 𝑏 = 2 𝑛log𝑏 𝑎 = 𝑛log2 1 = 𝑛0 = 1 vs. 𝑓 𝑛 = Θ(1) Case 2 (𝒌 = 𝟎): 𝑓 𝑛 = Θ 𝑛log𝑏 𝑎 lg 𝑘 𝑛 = Θ 1. lg 0 𝑛 = Θ(1) Thus, 𝑇 𝑛 = Θ lg 𝑛 11 Powering a Number Problem: Compute 𝑎𝑛 where 𝑛 ∈ ℕ Input: A real constant-sized number 𝑎 ∈ 𝑅 and exponent 𝑛 Output: 𝑎𝑛 Naïve Algorithm: 𝑎 × 𝑎 × ⋯ × 𝑎 Time = Θ(𝑛) Can we do better? 12 Powering a Number: Divide & Conquer Using Divide & Conquer, we can first write 𝑎𝑛 as follows: 𝑎𝑛 𝑛/2. 𝑎 𝑛/2 𝑎 = ቊ (𝑛−1)/2 (𝑛−1)/2 𝑎.𝑎.𝑎 if 𝑛 is even if 𝑛 is odd Divide: Divide 𝑛 by 2 Conquer: Recursively exponentiate the smaller terms Combine: Square the result of the sub-problem (and multiply by 𝑎 only if 𝑛 is odd) 13 Powering a Number: D&C Pseudocode 𝑛/2 𝑛/2 𝑎.𝑎 𝑎 = ቊ (𝑛−1)/2 𝑎. 𝑎(𝑛−1)/2. 𝑎 𝑛 if 𝑛 is even if 𝑛 is odd Pow 𝑎, 𝑛 : if 𝑛 is even then 𝑘 = 𝑛/2 𝑟 = Pow 𝑎, 𝑘 return 𝑟 × 𝑟 else if 𝑛 is odd then 𝑛−1 𝑘= 2 𝑟 = Pow 𝑎, 𝑘 return 𝑟 × 𝑟 × 𝑎 // Divide // Conquer // Combine // Divide // Conquer // Combine 14 Powering a Number: Divide & Conquer 𝑎𝑛 𝑛/2 𝑛/2 𝑎.𝑎 = ቊ (𝑛−1)/2 𝑎. 𝑎(𝑛−1)/2. 𝑎 310 Example: 35 × × 3 35 × ×3 32 3 if 𝑛 is even if 𝑛 is odd 3 32 × ×3 32 3 3 × × 3 3 32 × 3 15 Powering a Number: Running Time 𝑇 𝑛 = 𝑇 𝑛/2 + Θ 1 + Θ 1 Using Master Method ◦ 𝑓 𝑛 =Θ 1 𝑛log1 2 = 1 ◦ Looks like Case 2 so let us try it first: ◦ Is 𝑓 𝑛 = Θ 𝑛log1 2 lg 𝑘 𝑛 ? ◦ Yes, for 𝑘 = 0 ◦ So, it is Case 2 ◦ Therefore: 𝑇 𝑛 = Θ(lg 𝑛) Pow 𝑎, 𝑛 : if 𝑛 is even then 𝑘 = 𝑛/2 𝑟 = Pow 𝑎, 𝑘 return 𝑟 × 𝑟 else if 𝑛 is odd then 𝑛−1 𝑘= 2 𝑟 = Pow 𝑎, 𝑘 return 𝑟 × 𝑟 × 𝑎 // Divide Θ(1) // Conquer 𝑇(𝑛/2) // Combine Θ(1) // OR // Divide Θ(1) // Conquer 𝑇(𝑛/2) // Combine Θ(1) 16 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. 17