DIVIDE AND
CONQUER
1
DIVIDE & CONQUER
The most well known algorithm design strategy:
1. Divide the problem into two or more smaller
subproblems.
2. Conquer the subproblems by solving them
recursively.
3. Combine the solutions to the subproblems into the
solutions for the original problem.
GENERAL METHOD
Divide_Conquer(problem P)
{
if Small(P) return S(P);
else {
divide P into smaller instances P1, P2,
…,Pk, k≥1;
Apply Divide_Conquer to each of these subproblems;
return Combine(Divide_Conque(P1),
Divide_Conque(P2),…, Divide_Conque(Pk));
}
DIVIDE AND CONQUER
EXAMPLES
• Merge sort
• Quick sort
• Strassen’s Matrix Multiplication
MERGE SORT
The merge sort algorithm works from “the
bottom up”
• start by solving the smallest pieces of the
main problem
• keep combining their results into larger
solutions
• eventually the original problem will be
solved
8 3 2 9 7 1 5 4
8 3 2 9 7 1 5 4
8 3 2 9 71 5 4
8 3 2 9 7 1 5 4
3 8 2 9 1 7 4 5
2 3 8 9 1 4 5 7
1 2 3 4 5 7 8 9
TIME COMPLEXITY OF
MERGE SORT
T(n) = 2T(n/2)+cn
= 2(2T(n/4)+cn/2)+cn
= 4T(n/4)+2cn
= 4(2T(n/8)+cn/4)+2cn
= 8T(n/8)+3cn
.
.
=2kT(n/2k)+kcn = nT(1)+cn log n = an+ c nlog n = O(log n)
QUICKSORT
Given an array of n elements (e.g., integers):
If array only contains one element, return
Else
• pick one element to use as pivot.
• Partition elements into two sub-arrays:
• Elements less than or equal to pivot
• Elements greater than pivot
• Quicksort two sub-arrays
• Return results
EXAMPLE
We are given array of n integers to sort:
40 20 10 80 60 50 7 30 100
PICK PIVOT ELEMENT
There are a number of ways to pick the pivot
element. In this example, we will use the first
element in the array:
40 20 10 80 60 50 7 30 100
PARTITIONING ARRAY
Given a pivot, partition the elements of the array
such that the resulting array consists of:
1. One sub-array that contains elements >= pivot
2. Another sub-array that contains elements < pivot
The sub-arrays are stored in the original data
array.
Partitioning loops through, swapping elements
below/above pivot.
pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot]
++i
pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
3. If i < j swap data[i] and data[j]
pivot_index = 0 40 20 10 80 60 50 7 30 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
3. If i < j swap data[i] and data[j]
pivot_index = 0 40 20 10 30 60 50 7 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
3. If i < j swap data[i] and data[j]
4. While i < j, go to 1.
pivot_index = 0 40 20 10 30 60 50 7 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
3. If i < j swap data[i] and data[j]
4. While i < j, go to 1.
pivot_index = 0 40 20 10 30 60 50 7 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
3. If i < j swap data[i] and data[j]
4. While i < j, go to 1.
pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
3. If i < j swap data[i] and data[j]
4. While i < j, go to 1.
pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
3. If i < j swap data[i] and data[j]
4. While i < j, go to 1.
pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
3. If i < j swap data[i] and data[j]
4. While i < j, go to 1.
5. Swap data[j] and data[pivot_index]
pivot_index = 0 40 20 10 30 7 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
1. While data[i] <= data[pivot] ++i
2. While data[j] > data[pivot] --j
3. If i < j swap data[i] and data[j]
4. While i < j, go to 1.
5. Swap data[j] and data[pivot_index]
pivot_index = 4 7 20 10 30 40 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
i j
PARTITION RESULT
7 20 10 30 40 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
<= data[pivot] > data[pivot]
RECURSION: QUICKSORT
SUB-ARRAYS
7 20 10 30 40 50 60 80 100
[0] [1] [2] [3] [4] [5] [6] [7] [8]
<= data[pivot] > data[pivot]
ALGORITHM
Algorithm QUICKSORT(low, high)
{
if low < high then
{
j := PARTITION(a, low, high+1);
// j is the position of the partitioning element
QUICKSORT(low, j –1);
QUICKSORT(j + 1 , high);
}
}
Algorithm PARTITION(a, m, p)
{
V = a(m); i = m; j = p; // A (m) is the partition element
do
{
loop i := i + 1 until a(i) ≥ v
loop j := j –1 until a(j) ≤ v
if (i < j) then SWAP (a, i, j)
} while (i >j);
a[m] := a[j];
a[j] := V; // the partition element belongs at position P
return j;
}
Algorithm SWAP(a, i, j)
{
P:=a[i];
a[i] := a[j];
a[j] := p;
}
WORST CASE OF
QUICK SORT
TIME COMPLEXITY OF
QUICK SORT
Worst Case Analysis
T (n) = T (n –1) + cn n>1
= T(n-2) + c(n-1) + cn
= T(n-3) + c(n-2) + c(n-1) + cn
.
.
=T(1) + c(2) + c(3) + .. + c(n-2) + c(n-1) + cn
= T(1) + c(2+3+..+(n-1)+n) = O(n2)
TIME COMPLEXITY OF QUICK SORT
Best / Average Case Analysis
T(n) = 2T(n/2)+cn
= 2(2T(n/4)+cn/2)+cn
= 4T(n/4)+2cn
= 4(2T(n/8)+cn/4)+2cn
= 8T(n/8)+3cn
.
.
=2kT(n/2k)+kcn = nT(1)+cn log n
= an+ c nlog n = O(n log n)
Divide and Conquer
Strassen’s Matrix Multiplication
Matrix multiplication
The problem:
n n
Multiply two matrices A and B, each of size
A B C
nn nn nn
37
The traditional way:
n
C ij Aik Bkj
k 1
use three for-loop
T ( n) O ( n ) 3
38
The Divide-and-Conquer way: (n is power of 2)
C11 C12 A11 A12 B11 B12
C A B
C 21 C 22 A21 A22 B21 B22
C11 A11 B11 A12 B21
C12 A11 B12 A12 B22
C 21 A21 B11 A22 B21
C 22 A21 B12 A22 B22
transform the problem of multiplying A and B, each of size
n n
[n×n] into 8 subproblems, each of
size
2 2
39
n
T (n) 8 T ( ) an 2
2
O(n 3 )
which an2 is for addition
so, it is no improvement compared with the traditional
way
40
Example: 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
use Divide-and-Conquer way to solve it as following:
1 1 1 0 1 1 1 0 3 3 3 0
1 1 1 0 1 1 1 0 3 3 3 0
1 1 1 0 1 1 1 0 3 3 3 0
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 1 1 3 3
C11
1 1 1 1 1 0 0 0 3 3
1 1 1 0 1 0 1 0 3 0
C12
1 1 1 0 1 0 0 0 3 0
1 1 1 1 1 0 1 1 3 3
C 21
0 0 1 1 0 0 0 0 0 0
1 1 1 0 1 0 1 0 3 0
C 22
0 0 1 0 0 0 0 0 0 0
42
Strassen’s matrix multiplication:
· Discover a way to compute the Cij’s using 7
multiplications and 18 additions or subtractions
P ( A11 A22 )( B11 B22 )
Q ( A21 A22 ) B11
R A11 ( B12 B22 )
S A22 ( B21 B11 )
T ( A11 A12 ) B22
U ( A21 A11 )( B11 B12 )
V ( A12 A22 )( B21 B22 )
C11 P S T V
C12 R T
C 21 Q S
C 22 P R Q U
43
•Algorithm :
procedure Strassen (n, A, B, C) // n is size, A,B the input
matrices, C output matrix
begin
if n = 2,
C11 a11 b11 a12 b21;
C12 a11 b12 a12 b22 ;
C21 a21 b11 a22 b21;
C22 a21 b12 a22 b22 ;
else
(cont.)
44
else
Partition A into 4 submatrices: A11 , A12 , A21 ,; A22
Partition B into 4 submatrices: B11 , B12 , B21 , B
; 22
n
call Strassen ( , A11 A22 , B11 B22; , P )
2
n
call Strassen ( , A21 A22 , B11 , Q);
2
n
call Strassen ( , A11 , B12 B22; , R)
2
n
call Strassen ( , A22 , B21 B11; , S )
2
n
call Strassen ( , A11 A12 , B22
; ,T )
2
45
n
call Strassen ( , A21 A11 , B11 B12; , U )
2
n
call Strassen ( , A12 A22 , B21 B22; , V )
2
C11 P S T V ;
C12 R T ;
C 21 Q S ;
C 22 P R Q U ;
end;
46
Analysis:
n
7 T ( ) an 2 n2
T ( n) 2
b n2
n
T ( n) 7 T ( ) an 2
2
n 7
7 2 T ( 2 ) ( )an 2 an 2
2 4
n 7 7
7 3 T ( 3 ) ( ) 2 an 2 ( ) an 2 an 2
2 4 4
47
Assume n = 2k for some integer k
n 7
7 k 1 T ( k 1 ) an 2 ( ) k 2 1
2 4
7 k 1
k 1
( 4 ) 1
7 b an
2
7
1
4
7
b 7k c n2 ( )k
4
7
7 Lgn Lg
b 7 cn ( ) b 7 cn (n) 4
Lgn 2 Lgn 2
4
b n Lg 7 cn Lg 7 (b c) n Lg 7
O(n Lg 7 ) O(n 2.81 )
48
Example: 5 2 6 1 7 5 8 0
0 6 2 0 1 8 2 6
3 8 1 4 X 9 4 3 8
1 8 5 6 5 3 7 9
use Strassen’s matrix multiplication to solve it as
following:
49
50
51
52
53
54
