Divide and Conquer

Lecture No. 4

Dr. Javed Iqbal

 Divide and Conquer
 Binary Search
 Merge Sort
 Quick Sort
 French Emperor Napoleon employed the
divide and conquer strategy on Dec, 1805
 He fought with large army only with 15000
soldiers
 By dividing the large army into two small
groups, Napoleon able to conquer the large
army
 Similar approach is adopted on an instance of
problem
 Divide and conquer is a Top-Down approach
The most-well known algorithm design
strategy:
1. Divide instance of problem into two or
more smaller instances
2. Solve smaller instances recursively
3. Obtain solution to original (larger) instance
by combining these solutions

Distinction between divide and conquer and decrease and

conquer is somewhat vague. Dec/con typically does not solve
both subproblems.

4
 a problem of size n

subproblem 1 subproblem 2
of size n/2 of size n/2

a solution to a solution to
subproblem 1 subproblem 2

a solution to
the original problem
 Sorting: mergesort and quicksort
 Binary tree traversals
 Multiplication of large integers
 Matrix multiplication: Strassen’s algorithm
 Closest-pair and convex-hull algorithms

 Binary search: decrease-by-half (or degenerate

divide&conq.)

7
 Recursive version of binary search is used by
divide and conquer
 Binary Search can be summarized as follows:

If x equals the middle item, quit. Otherwise:

1. Divide the array into two subarrays about half as
large. If x is smaller than the middle item, choose the
left subarray. If x is larger than the middle item,
choose the right subarray.
2. Conquer (solve) the subarray by determining
whether x is in that subarray. Unless the subarray is
sufficiently small, use recursion to do this.
3. Obtain the solution to the array from the solution
to the subarray.
 Given value and sorted array a[], find index i
such that a[i] = value, or report that no such index exists.

 Invariant. Algorithm maintains a[lo]  value  a[hi].

 Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo hi
 Binary search. Given value and sorted array a[], find index i

such that a[i] = value, or report that no such index exists.

 Invariant. Algorithm maintains a[lo]  value  a[hi].

 Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo mid hi
 Binary search. Given value and sorted array a[], find index i

such that a[i] = value, or report that no such index exists.

 Invariant. Algorithm maintains a[lo]  value  a[hi].

 Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo hi
 Binary search. Given value and sorted array a[], find index i

such that a[i] = value, or report that no such index exists.

 Invariant. Algorithm maintains a[lo]  value  a[hi].

 Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo mid hi
 Binary search. Given value and sorted array a[], find index i

such that a[i] = value, or report that no such index exists.

 Invariant. Algorithm maintains a[lo]  value  a[hi].

 Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo hi
 Binary search. Given value and sorted array a[], find index i

such that a[i] = value, or report that no such index exists.

 Invariant. Algorithm maintains a[lo]  value  a[hi].

 Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo mid hi
 Binary search. Given value and sorted array a[], find index i

such that a[i] = value, or report that no such index exists.

 Invariant. Algorithm maintains a[lo]  value  a[hi].

 Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo
hi
 Binary search. Given value and sorted array a[], find index i

such that a[i] = value, or report that no such index exists.

 Invariant. Algorithm maintains a[lo]  value  a[hi].

 Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo
hi
mid
 Binary search. Given value and sorted array a[], find index i

such that a[i] = value, or report that no such index exists.

 Invariant. Algorithm maintains a[lo]  value  a[hi].

 Ex. Binary search for 33.

6 13 14 25 33 43 51 53 64 72 84 93 95 96 97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

lo
hi
mid
18
 Binary Search Runtime(s):

Worst case performance О(log n)

Best case performance O(1)
Average case performance O(Log n)
 BinarySearch(A[0..N-1], value, low, high)
{
if (high < low) return -1 // not found
mid = low + (high - low) / 2
if (A[mid] > value)
return BinarySearch(A, value, low, mid-1)
else if (A[mid] < value)
return BinarySearch(A, value, mid+1, high)
else
return mid // found
}
 Problem: Determine whether x is in the sorted array S of size n.
 Inputs: positive integer n, sorted (nondecreasing order) array of
keys S indexed from 1 to n, a key x.
 Outputs: location, the location of x in S (0 if x is not in S).
index location (index low, index high)
{
index mid;
if (low > high) return 0;
else {
mid = [(low + high)/2];
if (x == S[mid])
return mid ;
else if (x < S[mid])
return location(low, mid - 1);
else
return location(mid + 1, high);
}
}
 Divide and Conquer

Sort

Sort Sort

Sort Sort Sort Sort

Divide and Conquer

Combine

Combine Combine
module sort(array)
{
if (size of array > 1)
{
split(array, firstPart, secondPart)
sort(firstPart)
sort(secondPart)
combine(firstPart, secondPart)
}
}
 Merge sort is a divide and conquer algorithms
that does exactly that
 It split the list in parts.
 Merge sort , sorts the two parts
 Then merges the two sorted parts together.
 Merge sort can be implemented recursively.
 The merge sort algorithm involves three
steps.
 If the number of items to sort is 0 or 1, then
return.
 Recursively sort the first and second parts
separately.
 Merge the two sorted parts into a sorted
group.
Sort Sort

Merge
 array:

size
tmpArrayPtr:

tmp:
array[0] array[mid]

mid (size - mid)

firstPart : array

secondPart : array + mid

void mergeSort(int array[], int size)
{
int* tmpArrayPtr = new int[size];

if (tmpArrayPtr != NULL)
{
mergeSortRec(array, size, tmpArrayPtr);
}
else
{
cout<<“Not enough memory to sort list.<<;
retrun;
}

delete[]tmpArrayPtr;
}
void mergeSortRec(float array[], int size, float tmp[])
{
int i;
int mid = size/2;

if (size > 1)
{
mergeSortRec(array, mid, tmp);
mergeSortRec(array+mid, size-mid, tmp);

mergeArrays(array, mid, array+mid, size-mid, tmp);

for (i = 0; i < size; i++)

{
array[i] = tmp[i];
}
}
}
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50

aSize: 5 bSize: 6

tmp:
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=0 j=0

tmp:
k=0
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=0 j=0

tmp: 3
k=0
 Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=1 j=0

tmp: 3 5
k=1
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=2 j=0

tmp: 3 5 6
k=2
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=2 j=1

tmp: 3 5 6 10
k=3
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=2 j=2

tmp: 3 5 6 10 14
k=4
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=2 j=3

tmp: 3 5 6 10 14 15
k=5
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=3 j=3

tmp: 3 5 6 10 14 15 22
k=6
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=3 j=4

tmp: 3 5 6 10 14 15 22 28
k=7
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=4 j=4

tmp: 3 5 6 10 14 15 22 28 30
k=8
Example:

a: 3 5 15 28 30 b: 6 10 14 22 43 50
i=5 j=4

Done.

tmp: 3 5 6 10 14 15 22 28 30 43 50
k=9
void
mergeArrays(float a[],int aSize,float b[],int bSize,float tmp[])
{
int k, i = 0, j = 0;
for (k = 0; k < aSize + bSize; k++)
{
if (i == aSize) {
tmp[k] = b[j];
j++;
}
else if (j == bSize) {
tmp[k] = a[i];
i++;
}
else if (a[i] <= b[j]) {
tmp[k] = a[i];
i++;
}
else {
tmp[k] = b[j];
j++;
}
}
}
 Most of the work is in the merging.
 Takes O(n log(n))
 Uses more space than other sorts.
 Partition

x<p p p <= x
Sort Sort
Example:
array: 5 89 35 10 24 15 37 13 20 17 70

size: 11
Example:

array: 5 89 35 14 24 15 37 13 20 7 70

“pivot
element”
Example:

array: 5 89 35 14 24 15 37 13 20 7 70

partition:
5 89 35 14 24 15 37 13 20 7 70

7 14 5 13 15 35 37 89 20 24 70

index: 4
Example:
index: 4

array: 7 14 5 13 15 35 37 89 20 24 70
Example:
array[0] array[index + 1]

7 14 5 13 15 35 37 89 20 24 70

index (size - index - 1)

firstPart : array

secondPart : array + index + 1

void quickSort(float array[], int size)
{
int index;

if (size > 1)
{
index = partition(array, size);
quickSort(array, index);
quickSort(array+index+1, size - index - 1);
}
}
Example:
mid: 4

0
array: 5 89 35 14 24 15 37 13 20 7 70

15 89 35 14 24 5 37 13 20 7 70
Example:

0
array: 15 89 35 14 24 5 37 13 20 7 70

k=1
Example:

index:0

array: 15 89 35 14 24 5 37 13 20 7 70

k:1
Example:

index:0

array: 15 89 35 14 24 5 37 13 20 7 70

k:2
Example:

index:0

array: 15 89 35 14 24 5 37 13 20 7 70

k:3
Example:

index:1

array: 15 14
89 35 89
14 24 5 37 13 20 7 70

k:3
Example:

index:1

array: 15 14 35 89 24 5 37 13 20 7 70

k:4
Example:

index:1

array: 15 14 35 89 24 5 37 13 20 7 70

k:5
Example:

index:2

array: 15 14 35
5 89 24 35
5 37 13 20 7 70

k:5
Example:

index:2

array: 15 14 5 89 24 35 37 13 20 7 70

k:6
Example:

index:2

array: 15 14 5 89 24 35 37 13 20 7 70

k:7 etc...
Example:

index:4

array: 15 14 5 13 7 35 37 89 20 24 70

k:11
Example:

index:4

array: 15
7 14 5 13 15
7 35 37 89 20 24 70

x < 15 15 <= x
Example:
pivot now in
correct position

array: 15
7 14 5 13 15
7 35 37 89 20 24 70

x < 15 15 <= x
Example:

7 14 5 13 15 35 37 89 20 24 70

quickSort quickSort

7 14 5 13 35 37 89 20 24 70
int partition(float array[], int size)
{
int k;
int mid = size/2;
int index = 0;

swap(array, array+mid);

for (k = 1; k < size; k++)

{
if (list[k] < list[0])
{
index++;
swap(array+k, array+index);
}
}

swap(array, array+index);

return index;
}