Analysis and Design of Algorithm 2015

UNIT-3 Divide and Conquer

Topic:
Divide and Conquer Algorithm: Introduction, Recurrence and different methods to solve
recurrence, Multiplying large Integers Problem, Problem Solving using divide and conquer
algorithm - Binary Search, Max-Min problem, Sorting (Merge Sort, Quick Sort), Matrix
Multiplication, Exponential.

1. Introduction:
• Divide the problem into a number of sub-problems. There must be base case (to stop
recursion).
• Conquer (solve) each sub-problem recursively
• Combine (merge) solutions to sub-problems into a solution to the original problem

General Template for Divide and Conquer

Algorithm DandC(P)
{

If P is small enough return S(P);

else{

divide P into smaller instances P1,P2, ……Pk , k>=1;

apply DandC to each of these sub-problems;

return Combine (DandC(P1), DandC(P2), ……..DandC(Pk));

Time Complexity of divide and conquer:

T(n)= { T(1) n=1;

aT(n/b) + f(n) n>1;

Amit Kariyani & Hitesh Makwana Page 1

 Analysis and Design of Algorithm 2015

2. Recurrence solving methods:

Types of methods:
-Substitution Method
-Iteration Method
-Recursion Tree Method
-Master Method

2.1 Substitution Method: This is the method of solving recurrence in two steps:
- guess a bound (upper) or solution of problem(equation).
- use mathematical induction to prove our guess is correct.

Example 1:

T(n)= 2T(n/2)+n _________(1)

Guess that solution is T(n)=O(n*log(n)). This is upper bound of equation thus we have to prove
that

T(n)<=c*nlogn where c>0

By induction method assume that our assumption is true for n/2

Thus, T(n/2) <= c*(n/2)log(n/2) _______(2)

So put the value of T(n/2) into equation (1)

T(n) <= 2[c*(n/2)log(n/2)]+n

<= c*n log(n/2)+n

= c*n logn- c*n log2+n ( cause log(a/b)=log(a)-log(b))

= c*n logn- c*n+n

<= c*nlogn where c>=1

Hence, T(n)=O(n*log(n))

Using mathematical induction, we need to prove that our assumption holds true for base case
also

For n=1 T(n)<=0 because log(1)=0

Amit Kariyani & Hitesh Makwana Page 2

 Analysis and Design of Algorithm 2015

Example 2:

2.2 Iteration Method:

In iteration method the basic idea is to expand the recurrence and express it as a summation
of terms dependent only on n and the initial condition.

Example:

T(n)=2T(n/3)+n _____(1)
Expanding above terms

Iteration 1:

Assume n=n/3
T(n/3)=2T(n/9)+n/3 ____(2)

Put value of T(n/3) into equation (1)

T(n)=2[2T(n/9)+n/3]+n

= n+2/3n+4T(n/9) _________(3)

Iteration 2:

T(n)=n+2/3n+4/9n+8T(n/27) _________(4)

Amit Kariyani & Hitesh Makwana Page 3

 Analysis and Design of Algorithm 2015
Now, For n/3i <=1 so, n=3i

Taking log both the side,

log(n)=log(3i)

i=log(3)/log(n) from log rules

i=logn3

For nth iteration we can write,

T(n)=n+2/3n+(2/3)2n+8T(n/27)+……….+2logn3 T(1)

< = n ∑ (2/3)i +2logn3 O(1)

1
<= n ( ) + nlog23 O(1)
2
1−
3

<= 3n + O(n)

Thus, T(n)= O(n)

Amit Kariyani & Hitesh Makwana Page 4

 Analysis and Design of Algorithm 2015
Example: T(n)=3T(n/4)+n solve using Iteration method.

2.3 Recursion Tree Method:

Recurrence tree is just pictorial representation of iteration method.
T(n)=

2.4 Master Method:

Master Method is a direct way to get the solution.

T(n) = aT(n/b) + f(nc) where a >= 1 and b > 1

There are following three cases:

1. If f(n) = Θ(nc) where c < Logba then T(n) = Θ(nLogba)

2. If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n)
3.If f(n) = Θ(nc) where c > Logba then T(n) = Θ(f(n)) or Θ(nc)

Example 1:

• T(n) = 2T(n/2) + Θ(n)

Compare with T(n) = aT(n/b) + f(nc) Equation
c=1, a=2 and b=2
We get c=1 and Log22=1
Thus, case 2:
If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n)
• From this solution is : T(n)= Θ(nLog n)

Example 2:

• T(n) = T(n/2) + Θ(1)

• Compare with T(n) = aT(n/b) + f(nc) Equation

We get c=0 and Log21=0

Thus, case 2:

If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n)

• From this solution is : T(n)= Θ(Log n)

Amit Kariyani & Hitesh Makwana Page 5

 Analysis and Design of Algorithm 2015

3. Multiplying Large Integer Numbers:

If we have two numbers n1=1234 and n2=0981 both having size 4.
We dividing our problem into size/2
Assume, w=12, x=34, y=09, z=81

Thus, n1=wx and n2=yz

wx=1234=102w+x _________(1)

yz=0981=102y+z ___________(2)

Now, n1*n2=wx*yz

= (102w+x)* (102y+z)

= 104wy+102(wz+xy)+xz

=104(12*9)+ 102((12*81)+(34*9))+(34*81)

=1080000+127800+2754

=1210554

wy, wz, xy, xz total 4 multiplication required of n/2 size and 3 addition required to get
final answer

thus, time complexity of algorithm is

T(n)=4T(n/2)+O(n) assume 3 addition take O(n) time

Using master method solve this equation

a=4, b=2, c=1

Log24=2 and c=1

Thus case 1: c< Logba

Solution is T(n)= Θ(n Log42)= Θ(n2)

4. Binary Search:
The binary search algorithm begins by comparing the target value to value of the middle
element of the sorted array. If the target value is equal to the middle element's value, the
position is returned. If the target value is smaller, the search continues on the lower half of
the array, or if the target value is larger, the search continues on the upper half of the array.

Amit Kariyani & Hitesh Makwana Page 6

 Analysis and Design of Algorithm 2015
This process continues until the element is found and its position is returned, or there are no
more elements left to search for in the array and a "not found" indicator is returned.

Example :

Sorted array: A = [1, 3, 4, 6, 8, 9, 11] size of array is 7

Target value: X = 4
Iteration 1:
Compare X to 6(mid). X is smaller. Repeat with A = [1, 3, 4] size of array is 3
Iteration 2:
Compare X to 3(mid). X is larger. Repeat with A = [4] size of array is 1.
Iteration 3:
Compare X to 4(mid). X equals 4, so the position is returned.

Algorithm in c:

#include <stdio.h>

int main()
{
int i, first, last, middle, n, x, a[100];

printf("Enter number of elements\n");

scanf("%d",&n);

printf("Enter %d integers\n", n);

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

scanf("%d",&a[i]);

printf("Enter value to find\n");

scanf("%d", &x);

first = 0;
last = n - 1;
mid = (first+last)/2;

while (first <= last) {

if (a[mid] < x)
first = middle + 1;
else if (a[mid] == x) {
printf("%d found at location %d.\n", search, mid+1);
break;
}
else

Amit Kariyani & Hitesh Makwana Page 7

 Analysis and Design of Algorithm 2015
last = mid - 1;

mid = (first + last)/2;

}
if (first > last)
printf("Not found! %d is not present in the list.\n", search);

return 0;
}

Time Complexity:

From example we analyze that each iteration problem is divided into n/2i where i>1

Iteration 1: n elements

Iteration 2: n/2 elements

Iteration 3: n/4 elements

……………………….

………………………..

Thus, T(n)=T(n/2) +1

Solve using master method

T(n)=O(Log(n))

Binary search algorithm

Class Search algorithm

Data structure Array

Worst case performance O(log n)

Best case performance O(1)

Average case performance O(log n)

Amit Kariyani & Hitesh Makwana Page 8

 Analysis and Design of Algorithm 2015

5. Min-Max Problem:
Normal strategy (Needs 2n - 3 compares)
-Find MAX (n - 1 compares)
- Find MIN of the remaining elements (n - 2)
Divide and Conquer strategy
– Split the array in half
– Find the MAX and MIN of both halves
– Compare the 2 MAXes and compare the 2 MINs to get overall MAX and MIN.
• In this example, we only consider the number of comparisons and ignore all other
operations.
Example:
array: A = [8, 7, 2, 1, 5, 6, 3, 4] size of array is 8
Iteration 1:
Divide Array into [8, 7, 2, 1] and [5, 6, 3, 4]
From iteration 2 we get values max1=8 and max2=6 so final max=8
min1=1 and min2=3 so final min=1
Iteration 2:
Divide Array into [8,7] and [2,1]
Thus, max1=8, min1=7 and max2=2 and min2=1
So, final max=maximum(8,2)=8 and min=minimum(7,1)=1

Same as for second partition

Divide Array into [5,6] and [3,4]
Thus, max1=6, min1=5 and max2=4 and min2=3
So, final max=maximum(6,4)=6 and min=minimum(5,3)=3

Algorithm:

#include<stdio.h>
#include<conio.h>
maxmin(int,int,int,int);
int a[20],max,min,max1,min1;
main()
{ int n,i;
printf("enter number of elements in the array\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("enter the number\n");
scanf("%d",&a[i]);
}
maxmin(0,n-1,max,min);
printf("the maximum element is- %d\n",max);
printf("the minimum element is- %d\n",min);
getch();

Amit Kariyani & Hitesh Makwana Page 9

 Analysis and Design of Algorithm 2015
}
maxmin(int i,int j,int max,int min)
{
if(i=j)
{
max=min=a[i];
}

else if(j=i+1)
{
if(a[i]<a[j])
{
max=a[j]; min=a[i];
}
else
{
max=a[i]; min=a[j];
}
}
else
{
int mid=(i+j)/2;
maxmin(i,mid,max1,min1);
maxmin(mid+1,j,max2,min2);
min=minimum(min1,min2);
max= maximum(max1,max2);
}

}
int minimum(int m1,int m2)
{
if(m1<m2)
{
return m1 ;
}
else
{
return m2;
}
}
int miximum(int m1,int m2)
{
if(m1>m2)
{
return m1 ;
}

Amit Kariyani & Hitesh Makwana Page 10

 Analysis and Design of Algorithm 2015
else
{
return m2;
}
}
Time Complexity:

T(n)= 0 if n=1;

T(n)={ 1

2T(n/2) + 2
if n=2;

if n>2;

Using master method, T(n) = O(n)

6. Merge sort:
A merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is
considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist
remaining. This will be the sorted list.

Amit Kariyani & Hitesh Makwana Page 11

 Analysis and Design of Algorithm 2015

• Merge

[2, 3, 4, 5, 6, 7, 8, 10 ]

[3, 4, 6, 10] [2, 5, 7, 8]

[4, 10] [3, 6] [2, 8] [5, 7]

[4] [10] [3][6] [2][8] [5][7]

Algorithm in C:

#include<stdio.h>

void mergeSort(int a[],int low,int mid,int high);

void partition(int a[],int low,int high);

int main(){

int a[50],i,n;

printf("Enter the total number of elements: ");

scanf("%d",&n);

printf("Enter the elements which to be sort: ");

for(i=0;i<n;i++){
scanf("%d",&a[i]);
}

partition(a,0,n-1);

printf("After merge sorting elements are: ");

for(i=0;i<n;i++){
printf("%d ",a[i]);
}

return 0;
}

Amit Kariyani & Hitesh Makwana Page 12

 Analysis and Design of Algorithm 2015

void partition(int a[],int low,int high)

{
int mid;

if(low<high){
mid=(low+high)/2;
partition(a,low,mid);
partition(a,mid+1,high);
mergeSort(a,low,mid,high);
}
}

void mergeSort(int a[],int low,int mid,int high){

int i,j,c[MAX];
i=low;
j=mid+1;

while((i<=mid)&&(j<=high)){

if(a[i]<=a[j]){
c[k]=a[i];
i++;
k++;
}
else{
c[k]=a[j];
j++;
k++;
}
}

while(i<=mid)
{
c[k]=a[i];
i++;
k++;
}
while(j<=high)
{
c[k]=a[j];
j++;
k++;
}

Amit Kariyani & Hitesh Makwana Page 13

 Analysis and Design of Algorithm 2015
for(k=low;k<=high;k++){
a[k]=c[k];
}
}

Sample output:

Enter the total number of elements: 5

Enter the elements which to be sort: 2 5 0 9 1
After merge sorting elements are: 0 1 2 5 9

Time Complexity: using master method solve the recurrence

T(n)= 2T(n/2) + c2n if n>1, n=2k

T(n)=O(n*log(n)) for all cases (worst, average, best)

7. Quick Sort:
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:

Pick pivot point

There are a number of ways to pick the pivot element. In this example, we will use the first element
in the array:

Amit Kariyani & Hitesh Makwana Page 14

 Analysis and Design of Algorithm 2015

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

while(a[i]<pivot){

i++;}

while(a[j]>=pivot)

j—;

Interchange (a[i], a[j]) until i<j

Amit Kariyani & Hitesh Makwana Page 15

 Analysis and Design of Algorithm 2015

Interchange(pivot, a[j])

APPLY RECURRENCE ON SUB ARRAYS

Amit Kariyani & Hitesh Makwana Page 16

 Analysis and Design of Algorithm 2015
Algorithm:

#include<stdio.h>

void quicksort(int a[],int,int);

int main(){
int a[20],n,i;

printf("Enter size of the array: ");

scanf("%d",&n);

printf("Enter %d elements: ",n);

for(i=0;i<n;i++)
scanf("%d",&a[i]);

quicksort(a,0,n-1);

printf("Sorted elements: ");

for(i=0;i<n;i++)
printf(" %d",a[i]);

return 0;
}

void quicksort(int a[10],int first,int last){

int pivot,j,temp,i;

if(first<last){
pivot=first;
i=first;
j=last;

while(i<j){
while(a[i]<=x[pivot]&&i<last)
i++;
while(a[j]>x[pivot])
j--;
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}

temp=a[pivot];

Amit Kariyani & Hitesh Makwana Page 17

 Analysis and Design of Algorithm 2015
a[pivot]=a[j];
a[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);

}
}

Output:
Enter size of the array: 5
Enter 5 elements: 3 8 0 1 2
Sorted elements: 0 1 2 3 8
Time Complexity:
• Best case running time: O(n log2n)
• Worst case running time:
Recursion:
Partition splits array in two sub-arrays:
• one sub-array of size 0
• the other sub-array of size n-1
• Quicksort each sub-array
• Depth of recursion tree is O(n)
• Number of accesses per partition is O(n) so, total time T(n)=O(n2)

8. Matrix Multiplication (Strassen’s Matrix Multiplication):

It is faster than the standard matrix multiplication algorithm, but would be slower than the fastest
known algorithm for extremely large matrices, and is useful in practice for large matrices.

Matrix multiplication (Normal strategy)

Given two matrices A and B, the product of the two is a matrix C which is computed as follows:
C=AB

Amit Kariyani & Hitesh Makwana Page 18

 Analysis and Design of Algorithm 2015

Total 8-multiplication and 4-addition so, we can write

T(n)= 8T(n/2)+n
Using master method we can solve this equation T(n)=O(n3) [because case 1 of master method]
void MatMult()
{

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)
{
C[i][j] = 0.0;
for (int k = 0; k < p; k++)
C[i][j] += A[i][k] * B[k][j];
}
}

Total no. of loops in program is 3 nested loops are there

So, T(n)=O(n3)

Divide and conquer for matrix multiplication (Strassen’s algorithm):

To calculate the matrix product C = AB, Strassen's algorithm partitions the data to reduce the
number of multiplications performed
Here,
7- Multiplication and 18- Addition are required
The algorithm is described below.

1. Partition A, B and C into 4 equal parts:

A= A11 A12
A21 A22

B= B11 B12
B21 B22

C= C11 C12
C21 C22

Amit Kariyani & Hitesh Makwana Page 19

 Analysis and Design of Algorithm 2015

2. Evaluate the intermediate matrices:

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)

3. Construct C using the intermediate matrices:

C11 = P + S – T + V
C12 = R + T
C21 = Q + S
C22 = P – Q + R + U

Time Complexity:
Here, 7- Multiplication takes 7T(n/2) and 18- Addition takes 18n time then we can write

T(N)=7T(n/2)+18n
Solve using master method

T(n)= O(nlonba)=O(nlog27) [because case 1 of master method]

T(n)≈O(n2.81)

9. Exponential:

We wants to calculate an then power(a,n) is as below:

void power(a,n)
{
res=1
while(n>0)
{
res=res*a;
n--;
}
}
While loop iterate n times so time complexity of algorithm is T(n)=O(n)

Amit Kariyani & Hitesh Makwana Page 20

 Analysis and Design of Algorithm 2015

Now, Divide and conquer for finding exponential an

If n is even assume n=2k we can divide our problem like this

an=a2* a2* a2* a2………..* a2

If n is odd assume n=2k+1 we can divide our problem like this

an=a*a2* a2* a2* a2………..* a2

Algorithm for Exponential using Divide and conquer:
PowerDC(a.n)
{
res=1
while(n>0)
{
if(n%2!=0)
{
res=res*a;
n--;
}
if(n>0)
{
a=a*a;
n=n/2;
}
}
}

We are dividing our problem into n/2, n/4, ……1

So time complexity of algorithm is

T(n)=2T(n/2)+n (odd number calculation time)

Using master method solve this recurrence

T(n)=O(logn) [because case 2 of master method]

*************THE END**************

Amit Kariyani & Hitesh Makwana Page 21