Algorithms - Divide and Conquer Notes | EduRev

: Algorithms - Divide and Conquer Notes | EduRev

 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
)	

7 	


Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!