Divide and Conquer Techniques in Algorithms

cse 421 winter 2025 lecture 10 divide and conquer n.w
1 / 35
Embed
Share

Explore the concepts of Divide and Conquer in algorithms through Trominoes and Merge Sort examples. Understand base cases, divide steps, conquer strategies, and overall running time calculation in recursive problem-solving. Dive into the Tree Method used in Merge Sort for a deeper comprehension of algorithmic efficiency.

  • Algorithms
  • Divide and Conquer
  • Merge Sort
  • Trominoes
  • Recursion
rayaanacharya
penellope Follow

Uploaded on | 0 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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download 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.

E N D

Presentation Transcript

  1. CSE 421 Winter 2025 Lecture 10: Divide and Conquer 2 Nathan Brunelle http://www.cs.uw.edu/421

  2. Divide and Conquer (Trominoes) Base Case: For a 2 2 board, the empty cells will be exactly a tromino Divide: Break of the board into quadrants of size 2? 1 2? 1each Put a tromino at the intersection such that all quadrants have one occupied cell Conquer: Cover each quadrant Combine: Reconnect quadrants 2

  3. Divide and Conquer (Merge Sort) Base Case: If the list is of length 1 or 0, it s already sorted, so just return it (Alternative: when length is 15, use insertion sort) Divide: Split the list into two sublists of (roughly) equal length 5 5 8 2 9 4 1 Conquer: Sort both lists recursively 2 5 8 1 4 9 Combine: Merge sorted sublists into one sorted list 2 5 8 1 4 9 1 2 4 5 8 9 3

  4. Divide and Conquer (Running Time) Base Case: When the problem size is small ( ?), solve non-recursively ? = number of subproblems ? ?=size of each subproblem ??? = time to divide ? ? = ? Divide: When problem size is large, identify 1 or more smaller versions of exactly the same problem ? ? Conquer: Recursively solve each smaller subproblem Combine: Use the subproblems solutions to solve to the original ? ?+ ? ? where ? ? = ??? + ??(?) ? ? ??? =time to combine Overall: ? ? = ?? 4

  5. Divide and Conquer (Running Time) Base Case: When the problem size is small ( ?), solve non-recursively ? = number of subproblems ? ?=size of each subproblem ??? = time to divide ? ? = ? Divide: When problem size is large, identify 1 or more smaller versions of exactly the same problem ? ? Conquer: Recursively solve each smaller subproblem Combine: Use the subproblems solutions to solve to the original ? ?+ ? ?? where ??? + ??? ? ?? ? ? ??? =time to combine Overall: ? ? = ?? 5

  6. Tree Method (Merge Sort) ? 2 + ? ? ? = 2? Red box represents a problem instance Blue value represents time spent at that level of recursion ? ? comparisons / level ? ? 2 ? 2 ? 2 ? 2 log2? levels of recursion ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 1 1 1 1 1 1 1 1 1 1 1 1 log2? ? ? = ? = ?log? ?=0 6

  7. Tree Method (Slow CPP from last time) ? 2 + ?2 ? ? = 2? Red box represents a problem instance Blue value represents time spent at that level of recursion ?2 2i?2 22?=?2 level ? ? 2? work for ?2 22 ?2 22 ? 2 ? 2 log2? levels of recursion ?2 42 ?2 42 ?2 42 ?2 42 ? 4 ? 4 ? 4 ? 4 1 1 1 1 1 1 1 1 1 1 1 1 log2??2 2?= ?2 ? ? = ?=0 7

  8. Tree Method (More Subproblems) ? 2 + ? ? ? = 3? Red box represents a problem instance Blue value represents time spent at that level of recursion ? 3i? 2? work for level ? ? ? 2 ? 2 ? 2 ? 2 ? 2 ? 2 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 log2? ? 3 2 = ?log23 ?1.585 ? ? = ? 8 ?=0

  9. ? ? + ?? ? ? = ?? Tree Method Red box represents a problem instance Blue value represents time spent at that level of recursion ?? ? ???? ? children ??? work for level ? ? ? ? ? ?? ?? ?? ?? ?? ?2? ? ? ? ? ?? ?2? log?? levels of recursion ?? ?2? ? ?2 ? ?2 ? ?2 ? ?2 ?? ?2? ? ? c ? ? ? ? ? ? ? ? ? logb? ? ? ?? ?? ? ? = ?=0

  10. ? 2 + ? ? ? = 2? ? ??= log2? Work Stays Constant 2 21= 1 ? 1?= ?log? ? ? = ?=0 ? ? ? ? 2 ? 2 ? ? 2 ? 2 Total work is the work for any level, times the height ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 1 1 1 1 1 1 1 1 1 1 1 1 ? 10

  11. ? 2 + ?2 22=1 log2? ?21 ? ? = 2? ? ??= Work Decreases 2 2 ? = ?2 ? ? = 2 ?=0 ?2 ? ?2 ?21 ?2 22 ?2 22 ? 2 ? 2 2 Total work is asymptotically dominated by the root ?2 42 ?2 42 ?2 42 ?2 42 2 ? 4 ? 4 ? 4 ? 4 ?21 2 1 1 1 1 1 1 1 1 1 1 1 1 11

  12. ? 2 + ? 22=1 log2? ?21 ? ? = 3? ? ??= Work Increases 2 2 ? = ?2 ? ? = 2 ?=0 ? ? ? ? 2 ?3 ? 2 ? 2 ? 2 ? 2 ? 2 2 Total work is asymptotically dominated by the leaves ? 4 ? 4 ? 4 ? 4 2 ? 4 ? 4 3 2 ? 4 ? 4 ? 4 ? 4 ? 4 ? 4 ? 1 1 1 1 1 1 1 1 1 1 1 1 1 ?log?? 1 1 1 1 1 12

  13. Summary ? ??> 1 ? ??= 1 ? ??< 1 0 ??? ?? ?? When solving a recurrence of the form ? ? ? + ?? 1 1 ??? ??? ?? ? ? = ?? ? ? 2 2 ??? ??? The tree method will produce the series logb? ?? ? ? ? ? ?? ?? ? ? = ?? ?log??= ?log?? 1 ?=0 An asymptotic bound on ? ? then only depends on the value of ? (??log?) (??) (?log??) ??

  14. Solving Divide and Conquer Recurrences Master Theorem: Suppose that ? ? = ? ?(?/?) + ?(??)for ? > ?. If ? < ?? then ?(?) is ?(??) Cost is dominated by work at top level of recursion If ? = ?? then ?(?) is ?(?? log ?) Total cost is the same for all log?? levels of recursion If ? > ?? then ?(?) is ?(?log??) Note that log?? > ? in this case Cost is dominated by total work at lowest level of recursion Binary search:? = ?, ? = ?, ? = ? so ? = ??: Solution: ? ??log ? = ?(log ?) Mergesort: ? = ?, ? = ?, ? = ? so ? = ??: Solution: ?(??log ?)= ?(? log ?) 14

  15. Beware! It doesnt always apply! Master Theorem: Suppose that ? ? = ? ?(?/?) + ?(??)for ? > ?. If ? < ?? then ?(?) is ?(??) Cost is dominated by work at top level of recursion If ? = ?? then ?(?) is ?(?? log ?) Total cost is the same for all log?? levels of recursion If ? > ?? then ?(?) is ?(?log??) Note that log?? > ? in this case Cost is dominated by total work at lowest level of recursion ? 2 + ?2log? ? ? = 4? ? = ?, ? = ?, ? =??? 15

  16. Integer Multiplication 695273 123412 -------------------------------------------- 1390546 695273 2781092 2085819 1390546 695273 -------------------------------------------------- 85805031476 110110 101110 -------------------------------------------- 000000 110110 110110 110110 000000 110110 -------------------------------------------------- 100110110100 Elementary school algorithm ?(??) time for ?-bit integers Decimal Binary 16

  17. Divide and Conquer method ? 2 ? 2 110110 101110 + + = 2 = 2 ?1 ?2 ?1 ?2 ?1 ?2 ?1 ?2 2? ( ) + ?1 ?1 ? 2 + 2 ( ) + ?1 ?2 ?2 ?1 ( ) ?2 ?2 17

  18. Divide and Conquer (Integer Multiplication) Base Case: If there is only 1 place value, just multiply them Divide: Break the operands into 4 values: ?1 is the most significant ? ?2 is the least significant ? ?1 is the most significant ? ?2 is the most significant ? Conquer: Compute each of ?1?1, ?1?2, ?2?1, and ?2?2 ?1?1 ?1?2 ?2?1 ?2?2 + ?1 ?2 2 digits of ? 2 digits of ? 2 digits of ? 2 digits of ? ?1 ?2 ?1?1 ?1?2 ?2?1 ?2?2 Combine: Return 2??1?1 + 2 + ? 2 ?1?2+ ?2?1 + ?2?2 + 18

  19. Divide and Conquer (Integer Multiplication) Base Case: If there is only 1 place value, just multiply them Divide: Break the operands into 4 values: ?1 is the most significant ? ?2 is the least significant ? ?1 is the most significant ? ?2 is the most significant ? Conquer: Compute each of ?1?1, ?1?2, ?2?1, and ?2?2 ?1?1 ?1?2 ?2?1 ?2?2 + ?1 ?2 2 digits of ? 2 digits of ? 2 digits of ? 2 digits of ? ?1 ?2 ?1?1 ?1?2 ?2?1 ?2?2 Combine: Return 2??1?1 + 2 + ? 2 ?1?2+ ?2?1 + ?2?2 + 19

  20. Integer Multiplication Recurrence Solution Master Theorem: Suppose that ? ? = ? ?(?/?) + ?(??)for ? > ?. If ? < ?? then ?(?) is ?(??) Cost is dominated by work at top level of recursion If ? = ?? then ?(?) is ?(?? log ?) Total cost is the same for all log?? levels of recursion If ? > ?? then ?(?) is ?(?log??) Note that log?? > ? in this case Cost is dominated by total work at lowest level of recursion ? 2 ? ? = 4? + ? ? = ?, ? = ?, ? = ?, so ? > ??: Solution: ?(??????)= ?(??) 20

  21. Cant avoid these Karatsuba Method 2??1?1 + 2 ? 2 ?1?2+ ?2?1 + ?2?2 Can we do this with one multiplication? ?1+ ?2 ?1+ ?2 = ?1?1+ ?1?2+ ?2?1+ ?2?2 ?1?2+ ?2?1= ?1+ ?2 ?1+ ?2 ?1?1 ?2?2 Two multiplications One multiplication 21

  22. Divide and Conquer (Karatsuba Method) Base Case: If there is only 1 place value, just multiply them Divide: Break the operands into 4 values: ?1 is the most significant ? ?2 is the least significant ? ?1 is the most significant ? ?2 is the most significant ? Conquer: Compute each of ?1?1, ?1+ ?2 ?1+ ?2, and ?2?2 ?1+ ?2 2 digits of ? 2 digits of ? 2 digits of ? 2 digits of ? ?1 ?2 ?1 ?2 ?1+ ?2 ?1?1 ?1?2 ?2?2 ?1?1 Combine: Return 2??1?1 + 2 ?1+ ?2 ?1+ ?2 + ? 2 ?1?1 ?2?2 ?1+ ?2 ?1+ ?2 ?1?1 ?2?2 + ?2?2 22 + ?2?2

  23. Karatsuba Method Recurrence Solution Master Theorem: Suppose that ? ? = ? ?(?/?) + ?(??)for ? > ?. If ? < ?? then ?(?) is ?(??) Cost is dominated by work at top level of recursion If ? = ?? then ?(?) is ?(?? log ?) Total cost is the same for all log?? levels of recursion If ? > ?? then ?(?) is ?(?log??) Note that log?? > ? in this case Cost is dominated by total work at lowest level of recursion ? 2 ? ? = 3? + ? ? = ?, ? = ?, ? = ?, so ? > ??: Solution: ?(??????)= ? ??????= ? ?1.585 23

  24. Matrix Multiplication ? 1 4 7 2 5 8 3 6 9 2 8 4 6 ? 10 16 12 18 14 1 2 + 2 8 + 3 16 1 4 + 2 10 + 3 16 1 6 + 2 12 + 3 18 = 60 132 204 72 162 252 84 192 300 = Run time? ?(?3) 24

  25. Multiplying Matrices for ? ? to ? for ? ? to ? ?[?,?] ? for ? ? to ? endfor endfor endfor ?[?,?] ?[?,?] + ?[?,?] ?[?,?] Can we improve this with divide and conquer? 25

  26. We can see subproblems! ?11 ?11 ?11 ?21 ?31 ?41 ?12 ?22 ?32 ?42 ?13 ?23 ?33 ?43 ?14 ?24 ?34 ?44 ?11 ?21 ?31 ?41 ?12 ?22 ?32 ?42 ?13 ?23 ?33 ?43 ?14 ?24 ?34 ?44 ? = ? = ? ? = ?11 ?11 ?11 ?11 ?11?11+ ?12?21+ ?13?31+ ?14?41 ?21?11+ ?22?21+ ?23?31+ ?24?41 ?31?11+ ?32?21+ ?33?31+ ?34?41 ?41?11+ ?42?21+ ?43?31+ ?44?41 ?11?12+ ?12?22+ ?13?32+ ?14?42 ?21?12+ ?22?22+ ?23?32+ ?24?42 ?31?12+ ?32?22+ ?33?32+ ?34?42 ?41?12+ ?42?22+ ?43?32+ ?44?42 26

  27. Matrix Multiplication D&C Multiply ? ? matrices (? and ?) ?11 ?21 ?31 ?41 ?12 ?22 ?32 ?42 ?13 ?23 ?33 ?43 ?14 ?24 ?34 ?44 ?11 ?21 ?31 ?41 ?12 ?22 ?32 ?42 ?13 ?23 ?33 ?43 ?14 ?24 ?34 ?44 ?11 ?12 ?11 ?12 ? = ? = ?21 ?22 ?21 ?22 ?11 ?11+ ?12 ?21 ?21 ?11+ ?22 ?21 ?11 ?12+ ?12 ?22 ?21 ?12+ ?22 ?22 ? ? = 27

  28. Divide and Conquer Matrix Multiplication Base Case: For a 1 1 matrices, return the product in a 1 1 matrix Divide: Use each quadrant of the input ? ?matrices as it s own ? 2matrix Conquer: Compute each of: ?5 ?6 ?7 ?8 ?11 ?12 ?11 ?12 ?21 ?22 ?21 ?22 2 ? ?1= ?11 ?11 ?2= ?12 ?21 ?3= ?11 ?12 ?4= ?12 ?22 ?5= ?21 ?11 ?6= ?22 ?21 ?7= ?21 ?12 ?8= ?22 ?22 ?1 ?2 ?3 ?4 Combine: Compute the value of each quadrant by summing ?1 ?8 as shown ?1+ ?2 ?3+ ?4 ?5+ ?6 ?7+ ?8 28

  29. Karatsuba Method Recurrence Solution Master Theorem: Suppose that ? ? = ? ?(?/?) + ?(??)for ? > ?. If ? < ?? then ?(?) is ?(??) Cost is dominated by work at top level of recursion If ? = ?? then ?(?) is ?(?? log ?) Total cost is the same for all log?? levels of recursion If ? > ?? then ?(?) is ?(?log??) Note that log?? > ? in this case Cost is dominated by total work at lowest level of recursion ? 2 + ?2 ? ? = 8? ? = ?, ? = ?, ? = ?, so ? > ??: Solution: ?(??????)= ? ??????= ? ?3 29

  30. How to Improve? Multiply ? ? matrices (? and ?) ?11 ?21 ?31 ?41 ?12 ?22 ?32 ?42 ?13 ?23 ?33 ?43 ?14 ?24 ?34 ?44 ?11 ?21 ?31 ?41 ?12 ?22 ?32 ?42 ?13 ?23 ?33 ?43 ?14 ?24 ?34 ?44 ?11 ?12 ?11 ?12 ? = ? = ?21 ?22 ?21 ?22 ?11 ?11+ ?12 ?21 ?21 ?11+ ?22 ?21 ?11 ?12+ ?12 ?22 ?21 ?12+ ?22 ?22 ? ? = Idea: Use an idea like Karatsuba! Can we derive these products using addition/subtraction? 30

  31. Strassens Algorithm ?11 ?12 ?21 ?22 ?31 ?32 ?41 ?42 ?11 ?21 ?31 ?41 ?12 ?22 ?32 ?42 ?13 ?23 ?33 ?43 ?14 ?24 ?34 ?44 ?13 ?23 ?33 ?43 ?14 ?24 ?34 ?44 ?11 ?12 ?11 ?12 ? = ? = ?21 ?22 ?21 ?22 Find ? ?: Calculate: ?1= ?11+ ?22 (?11+ ?22) ?2= ?21+ ?22 ?11 ?3= ?11 (?12 ?22) ?4= ?22 (?21 ?11) ?5= ?11+ ?12 ?22 ?1,1?1,1+ ?1,2?2,1 ?2,1?1,1+ ?2,2?2,1 ?1,1?1,2+ ?1,2?2,2 ?2,1?1,2+ ?2,2?2,2 = ?1+ ?4 ?5+ ?7 ?2+ ?4 ?3+ ?5 ?1 ?2+ ?3+ ?6 ?6= ?21 ?11 (?11+ ?12) ?7= ?12 ?22 (?21+ ?22) 31

  32. Divide and Conquer Matrix Multiplication Base Case: For a 32 32 matrices, use the textbook algorithm Divide: Use each quadrant of the input ? ?matrices as it s own ? Conquer: Compute each of: ?1 ?2 ?3 ?4 ?11 ?12 ?11 ?12 2 ? 2matrix ?21 ?22 ?21 ?22 ?1= ?11+ ?22 (?11+ ?22) ?2= ?21+ ?22 ?11 ?3= ?11 (?12 ?22) ?4= ?22 (?21 ?11) ?5= ?11+ ?12 ?22 ?6= ?21 ?11 (?11+ ?12) ?7= ?12 ?22 (?21+ ?22) ?5 ?6 ?7 Combine: Compute the value of each quadrant by summing ?1 ?8 as shown ?1+ ?4 ?5+ ?7 ?3+ ?5 ?2+ ?4 ?1 ?2+ ?3+ ?6 32

  33. Karatsuba Method Recurrence Solution Master Theorem: Suppose that ? ? = ? ?(?/?) + ?(??)for ? > ?. If ? < ?? then ?(?) is ?(??) Cost is dominated by work at top level of recursion If ? = ?? then ?(?) is ?(?? log ?) Total cost is the same for all log?? levels of recursion If ? > ?? then ?(?) is ?(?log??) Note that log?? > ? in this case Cost is dominated by total work at lowest level of recursion ? 2 + ?2 ? ? = 7? ? = ?, ? = ?, ? = ?, so ? > ??: Solution: ?(??????)= ? ??????= ? ?2.807 33

  34. Strassens Algorithm ?3 ?log27 34

  35. Every few years someone comes up with an asymptotically faster algorithm Is this the fastest? Current best is ? ?2.3728596, but it requires input sizes in the millions to actually be faster We know there is no algorithm with running time ? ?2 The best possible running time is unknown! (and weirdly, may not exist!) 35

Related


No related presentations.

More Related Content