Page 1 CSE 421 Algorithms: Divide and Conquer Larry Ruzzo Thanks to Paul Beame, Kevin Wayne for some slides Page 2 CSE 421 Algorithms: Divide and Conquer Larry Ruzzo Thanks to Paul Beame, Kevin Wayne for some slides 4 algorithm design paradigms: divide and conquer Outline: General Idea Review of Merge Sort Why does it work? Importance of balance Importance of super-linear growth Some interesting applications Closest points Integer Multiplication Finding & Solving Recurrences Page 3 CSE 421 Algorithms: Divide and Conquer Larry Ruzzo Thanks to Paul Beame, Kevin Wayne for some slides 4 algorithm design paradigms: divide and conquer Outline: General Idea Review of Merge Sort Why does it work? Importance of balance Importance of super-linear growth Some interesting applications Closest points Integer Multiplication Finding & Solving Recurrences 5 algorithm design techniques Divide & Conquer Reduce problem to one or more sub-problems of the same type Typically, each sub-problem is at most a constant fraction of the size of the original problem Subproblems typically disjoint Often gives signi?cant, usually polynomial, speedup Examples: Mergesort, Binary Search, Strassen’s Algorithm, Quicksort (roughly) Page 4 CSE 421 Algorithms: Divide and Conquer Larry Ruzzo Thanks to Paul Beame, Kevin Wayne for some slides 4 algorithm design paradigms: divide and conquer Outline: General Idea Review of Merge Sort Why does it work? Importance of balance Importance of super-linear growth Some interesting applications Closest points Integer Multiplication Finding & Solving Recurrences 5 algorithm design techniques Divide & Conquer Reduce problem to one or more sub-problems of the same type Typically, each sub-problem is at most a constant fraction of the size of the original problem Subproblems typically disjoint Often gives signi?cant, usually polynomial, speedup Examples: Mergesort, Binary Search, Strassen’s Algorithm, Quicksort (roughly) merge sort MS(A: array[1..n]) returns array[1..n] { If(n=1) return A; New U:array[1:n/2] = MS(A[1..n/2]); New L:array[1:n/2] = MS(A[n/2+1..n]); Return(Merge(U,L)); } Merge(U,L: array[1..n]) { New C: array[1..2n]; a=1; b=1; For i = 1 to 2n C[i] = “smaller of U[a], L[b] and correspondingly a++ or b++”; Return C; } 6 A U C L split sort merge Page 5 CSE 421 Algorithms: Divide and Conquer Larry Ruzzo Thanks to Paul Beame, Kevin Wayne for some slides 4 algorithm design paradigms: divide and conquer Outline: General Idea Review of Merge Sort Why does it work? Importance of balance Importance of super-linear growth Some interesting applications Closest points Integer Multiplication Finding & Solving Recurrences 5 algorithm design techniques Divide & Conquer Reduce problem to one or more sub-problems of the same type Typically, each sub-problem is at most a constant fraction of the size of the original problem Subproblems typically disjoint Often gives signi?cant, usually polynomial, speedup Examples: Mergesort, Binary Search, Strassen’s Algorithm, Quicksort (roughly) merge sort MS(A: array[1..n]) returns array[1..n] { If(n=1) return A; New U:array[1:n/2] = MS(A[1..n/2]); New L:array[1:n/2] = MS(A[n/2+1..n]); Return(Merge(U,L)); } Merge(U,L: array[1..n]) { New C: array[1..2n]; a=1; b=1; For i = 1 to 2n C[i] = “smaller of U[a], L[b] and correspondingly a++ or b++”; Return C; } 6 A U C L split sort merge why balanced subdivision? Alternative "divide & conquer" algorithm: Sort n-1 Sort last 1 Merge them T(n) = T(n-1)+T(1)+3n for n = 2 T(1) = 0 Solution: 3n + 3(n-1) + 3(n-2) … = T(n 2 ) 7Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!