Introduction to Divide and Conquer Algorithms

Explore the Divide and Conquer method in algorithm design, focusing on Mergesort as a fast sorting recursive algorithm. Learn how to divide input into smaller parts, solve them recursively, and merge the results to obtain the final solution. Dive into the key ideas, steps, and intricacies of Merge operations, offering insights into sorting arrays efficiently.

• Divide and Conquer
• Mergesort
• Algorithm Design
• Recursive
• Sorting

deandrae Follow

Uploaded on Sep 11, 2024 | 2 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Lecture 19 Recap part A CS 161 Design and Analysis of Algorithms Ioannis Panageas

2. Divide and conquer method Steps of method: Divide input into parts (smaller problems) Conquer (solve) each part recursively Combine results to obtain solution of original T(n)= divide time + T(n1)+T(n2)+...+T(nk) + combine time Design and Analysis of Algorithms

3. Mergesort - A fast sorting recursive Algorithm Key idea: Divide input into two parts of equal size Sort each part recursively Merge the two sorted parts to obtain the solution. Example: Sort the following 11 numbers 9 3 4 220 1 3 10 5 8 7 2 Divide Recursion Merge Design and Analysis of Algorithms

4. Mergesort - A fast sorting recursive Algorithm Key idea: Divide input into two parts of equal size Sort each part recursively Merge the two sorted parts to obtain the solution. Example: Sort the following 11 numbers 9 3 4 220 1 3 10 5 8 7 2 9 3 4 220 1 3 10 5 8 7 2 Divide Recursion Merge Design and Analysis of Algorithms

5. Mergesort - A fast sorting recursive Algorithm Key idea: Divide input into two parts of equal size Sort each part recursively Merge the two sorted parts to obtain the solution. Example: Sort the following 11 numbers 9 3 4 220 1 3 10 5 8 7 2 9 3 4 220 1 3 10 5 8 7 2 Divide 1 3 4 9 220 2 3 5 7 8 10 Recursion Merge Design and Analysis of Algorithms

6. Mergesort - A fast sorting recursive Algorithm Key idea: Divide input into two parts of equal size Sort each part recursively Merge the two sorted parts to obtain the solution. Example: Sort the following 11 numbers 9 3 4 220 1 3 10 5 8 7 2 9 3 4 220 1 3 10 5 8 7 2 Divide 1 3 4 9 220 2 3 5 7 8 10 Recursion 1 2 3 3 4 5 7 8 9 10 220 Merge Design and Analysis of Algorithms

7. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. Design and Analysis of Algorithms

8. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

9. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

10. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

11. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

12. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

13. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

14. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

15. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

16. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

17. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

18. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

19. Mergesort - A fast sorting recursive Algorithm Tricky part: Merge Problem: Given two sorted arrays ?,?, merge them to a sorted array ?. Running time: ?(?) 1 3 4 9 220 2 3 5 7 8 10 Design and Analysis of Algorithms

20. Mergesort Pseudocode: Running time: How to analyze? Design and Analysis of Algorithms

21. Master theorem The Master Theorem can find the order of ?(?) which is defined recursively. Design and Analysis of Algorithms

22. Master theorem The Master Theorem can find the order of ?(?) which is defined recursively. Key idea: The answer depends on the comparison between ?(?) and ?log?? . So, there are 3 cases! Design and Analysis of Algorithms

23. Master theorem Case 1: ?log??dominates?(?) Design and Analysis of Algorithms

24. Master theorem Case 2: ?log??have same order as?(?) (up to log??) Design and Analysis of Algorithms

25. Master theorem Case 3: ?log??is dominated by?(?) (+ another condition) Design and Analysis of Algorithms

26. Case study: Maxima Set Problem: We are given ? points (?1,?1), ,(??,??) on the plane. A point (??,??) is called a maximum point if there is no other point (??,??) that ?? ?? and ?? ??. Example: ? captures pool size and ? restaurant quality. 10 hotels Design and Analysis of Algorithms

27. Case study: Maxima Set Problem: We are given ? points (?1,?1), ,(??,??) on the plane. A point (??,??) is called a maximum point if there is no other point (??,??) that ?? ?? and ?? ??. Example: ? captures pool size and ? restaurant quality. 10 hotels Explanation: ?,?,?,?,? are maximum points. ?,?,?,?,? are not. Design and Analysis of Algorithms

28. Case study: Maxima Set Problem: We are given ? points (?1,?1), ,(??,??) on the plane. A point (??,??) is called a maximum point if there is no other point (??,??) that ?? ?? and ?? ??. Idea: Divide and conquer. Divide step and Combine step is challenging. Design and Analysis of Algorithms

29. Case study: Maxima Set Divide step: It should split the points in two parts of equal size. How? Design and Analysis of Algorithms

30. Case study: Maxima Set Divide step: It should split the points in two parts of equal size. How? Choose the middle (median) point with respect to ? coordinates. Design and Analysis of Algorithms

31. Case study: Maxima Set Divide step: It should split the points in two parts of equal size. How? Choose the middle (median) point with respect to ? coordinates. Combine step: Return ?1 ?2? Design and Analysis of Algorithms

32. Case study: Maxima Set Combine step: Return ?1 ?2? Wrong: blue points below of ?1 are not part of the solution Design and Analysis of Algorithms

33. Case study: Maxima Set Combine step idea: ?2 points should part of the solution. From ?1, the points that are maximum should not be dominated by smallest with respect to x coordinates in ?2 Design and Analysis of Algorithms

34. Case study: Maxima Set Pseudocode: Running time?? Design and Analysis of Algorithms

35. Dynamic Programming Technique for solving optimization problems. Solve problem by solving sub-problems and combine: This is called Optimal substructure property. Design and Analysis of Algorithms

36. Dynamic Programming Technique for solving optimization problems. Solve problem by solving sub-problems and combine: This is called Optimal substructure property. Similar to divide-and-conquer: recursion (for solving sub-problems) Sub-problems overlap: solve them only once! DP = recursion + re-use (Memoization) Design and Analysis of Algorithms

37. Case study II: 0/1 Knapsack Problem: A set of ? items, with each item ? having positive weight ?? and positive benefit ??. You are asked to choose items with maximum total benefit so that the total weight is at most ? knapsack with 9 lbs capacity cover-small Items: Weight: Benefit: Solution: item 5 ($80, 2 lbs) item 3 ($6, 2lbs) item 1 ($20, 4lbs) 4 lbs $20 2 lbs $3 2 lbs $6 6 lbs 2 lbs $25 $80 Design and Analysis of Algorithms

38. Case study II: 0/1 Knapsack Idea: Dynamic Programming (first attempt). Step 1: Define the problem and subproblems. Answer: Let ??[?] be the maximum value I can get from items {1, ,?} without exceeding ?. Step 2: Define the goal/output given Step 1. It is ??[?]. Step 3: Define the base cases It is ??[0] = 0. Step 4: Define the recurrence Design and Analysis of Algorithms

39. Case study II: 0/1 Knapsack Idea: Dynamic Programming (first attempt). Step 4: Define the recurrence Item ? will be used or not. ??[?] = max(??[? 1],??[? 1] + ??) But how do we know that DP[k-1] does not exceed ? ?? in weight so we can use ?? Design and Analysis of Algorithms

40. Case study II: 0/1 Knapsack Idea: Dynamic Programming (correct attempt). Step 1: Define the problem and subproblems. Answer: Let ??[?,?] be the maximum value I can get from items {1, ,?} without exceeding ?. Design and Analysis of Algorithms

41. Case study II: 0/1 Knapsack Idea: Dynamic Programming (correct attempt). Step 1: Define the problem and subproblems. Answer: Let ??[?,?] be the maximum value I can get from items {1, ,?} without exceeding ?. Step 2: Define the goal/output given Step 1. It is ??[?,?]. Design and Analysis of Algorithms

42. Case study II: 0/1 Knapsack Idea: Dynamic Programming (correct attempt). Step 1: Define the problem and subproblems. Answer: Let ??[?,?] be the maximum value I can get from items {1, ,?} without exceeding ?. Step 2: Define the goal/output given Step 1. It is ??[?,?]. Step 3: Define the base cases It is ??[0,?] = 0 for all ? and ??[?,0] = 0 for all ?. Step 4: Define the recurrence Design and Analysis of Algorithms

43. Case study II: 0/1 Knapsack Idea: Dynamic Programming (correct attempt). Step 4: Define the recurrence Item ? will be used or not. ?? ? [?] = max(??[? ?][? ??] + ??,??[? ?][?]) Design and Analysis of Algorithms

44. Case study II: 0/1 Knapsack Idea: Dynamic Programming (correct attempt). Step 4: Define the recurrence Item ? will be used or not. ?? ? [?] = max(??[? ?][? ??] + ??,??[? ?][?]) Question: How do we know that item ? does not have weight more than ?? Design and Analysis of Algorithms

45. Case study II: 0/1 Knapsack Idea: Dynamic Programming (correct attempt). Step 4: Define the recurrence Item ? will be used or not. ??[?][?] = if ?? ?max(??[? ?][? ??] + ??,??[? ?][?]) If ??> ???[? ?][?] Answer: Add an if statement in the recurrence. Design and Analysis of Algorithms

46. Case study II: 0/1 Knapsack j=0 1 2 3 4 i=0 0 0 0 0 0 1 0 2 0 3 0

47. Case study II: 0/1 Knapsack j=0 1 2 3 4 i=0 0 0 0 0 0 0 (? < ?1) 1 0 0 (? < ?2) 2 0 0 (? < ?3) 3 0

48. Case study II: 0/1 Knapsack j=0 1 2 3 4 i=0 0 0 0 0 0 max(0,?1+0) 1 0 0 2 0 0 3 0 0

49. Case study II: 0/1 Knapsack j=0 1 2 3 4 i=0 0 0 0 0 0 1 0 0 1 max(1,?2+0) 2 0 0 3 0 0

50. Case study II: 0/1 Knapsack j=0 1 2 3 4 i=0 0 0 0 0 0 1 0 0 1 2 0 0 1 1 (? < ?3) 3 0 0

Load More ...