Design & Analysis of Algorithm

Divide & Conquer

 Divide the problem into a number of sub-problems

 Similar sub-problems of smaller size

 Conquer the sub-problems

 Solve the sub-problems recursively

 Sub-problem size small enough  solve the problems in straightforward manner

 Combine the solutions of the sub-problems

 Obtain the solution for the original problem

 Divide
 Divide the n-element sequence to be sorted into two subsequences of
n/2 elements each
 Conquer
 Sort the subsequences recursively using merge sort
 When the size of the sequences is 1 there is nothing more to do
 Combine

 Merge the two sorted subsequences

Alg.: MERGE-SORT(A, p, 5 2 4 7 1 3 2 6
r)
Check for base case
if p < r
Divide
then q ← (p + r)/2
Conquer
MERGE-SORT(A, p, q)
Conquer
MERGE-SORT(A, q + 1, r)
Combine
MERGE(A, p, q, r)

 Initial call: MERGE-SORT(A, 1, n)

Divide
1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6 q=4

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6
 Example – n Power of 2

Conquer
1 2 3 4 5 6 7 8

1 2 2 3 4 5 6 7
and
Merge 1 2 3 4 5 6 7 8

2 4 5 7 1 2 3 6

1 2 3 4 5 6 7 8

2 5 4 7 1 3 2 6

1 2 3 4 5 6 7 8

5 2 4 7 1 3 2 6
 Example – n Not a Power of 2
1 2 3 4 5 6 7 8 9 10 11

4 7 2 6 1 4 7 3 5 2 6 q=6
Divide
1 2 3 4 5 6 7 8 9 10 11

q=3 4 7 2 6 1 4 7 3 5 2 6 q=9

1 2 3 4 5 6 7 8 9 10 11

4 7 2 6 1 4 7 3 5 2 6

1 2 3 4 5 6 7 8 9 10 11

4 7 2 6 1 4 7 3 5 2 6

1 2 4 5 7 8

4 7 6 1 7 3
 Example – n Not a Power of 2

Conquer
1 2 3 4 5 6 7 8 9 10 11

1 2 2 3 4 4 5 6 6 7 7
and
Merge 1
1 2 3 4 5 6 7 8 9 10 11

2 4 4 6 7 2 3 5 6 7

1 2 3 4 5 6 7 8 9 10 11

2 4 7 1 4 6 3 5 7 2 6

1 2 3 4 5 6 7 8 9 10 11

4 7 2 1 6 4 3 7 5 2 6

1 2 4 5 7 8

4 7 6 1 7 3