`

Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

DIVIDE AND CONQUER:

General method:

• Given a function to compute on ‘n’ inputs the divide-and-conquer strategy suggests

splitting the inputs into ‘k’ distinct subsets, 1<k<=n, yielding ‘k’ sub problems.

• These sub problems must be solved, and then a method must be found to combine
sub solutions into a solution of the whole.

• If the sub problems are still relatively large, then the divide-and-conquer strategy
can possibly be reapplied.

• Often the sub problems resulting from a divide-and-conquer design are of the same
type as the original problem.
• For those cases the re application of the divide-and-conquer principle is naturally
expressed by a recursive algorithm.
• D And C(Algorithm) is initially invoked as D and C(P), where ‘p’ is the problem to

VTUPulse.com
•

•
•
be solved.
Small(P) is a Boolean-valued function that determines whether the i/p size is small
enough that the answer can be computed without splitting.
If this so, the function ‘S’ is invoked.
Otherwise, the problem P is divided into smaller sub problems.
• These sub problems P1, P2 …Pk are solved by recursive application of D And C.
• Combine is a function that determines the solution to p using the solutions to the ‘k’
sub problems.
• If the size of ‘p’ is n and the sizes of the ‘k’ sub problems are n1, n2 ….nk,
respectively, then the computing time of D And C is described by the recurrence
relation.

T(n)= { g(n) n small

T(n1)+T(n2)+……………+T(nk)+f(n); otherwise.
1
Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

1. Algorithm D And C(P)

2. {
3. if small(P) then return S(P);
4. else
5. {
6. divide P into smaller instances
P1, P2… Pk, k>=1;
7. Apply D And C to each of these sub problems;
8. return combine (D And C(P1), D And C(P2),…….,D And C(Pk));
9. }
10. }

• The complexity of many divide-and-conquer algorithms is given by recurrences of

the form
T(n) = { T(1) n=1

VTUPulse.com AT(n/b)+f(n) n>1

• One of the methods for solving any such recurrence relation is called the
substitution method.
• This method repeatedly makes substitution for each occurrence of the function. T
is the Right-hand side until all such occurrences disappear.

Example:

1) Consider the case in which a=2 and b=2. Let T(1)=2 & f(n)=n.
We have,
T(n) = 2T(n/2)+n
= 2[2T(n/2/2)+n/2]+n
2

= [4T(n/4)+n]+n
Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

= 4T(n/4)+2n
= 4[2T(n/4/2)+n/4]+2n
= 4[2T(n/8)+n/4]+2n
= 8T(n/8)+n+2n
= 8T(n/8)+3n
*

• In general, we see that T(n)=2^iT(n/2^i )+in., for any log n >=I>=1.

T(n) =2^log n T(n/2^log n) + n log n

Corresponding to the choice of i=log n

VTUPulse.com
Thus, T(n) = 2^log n T(n/2^log n) + n log n

= n. T(n/n) + n log n

= n. T(1) + n log n [since, log 1=0, 2^0=1] = 2n + n

log n

BINARY SEARCH

1. Algorithm Bin search(a,n,x)

2. // Given an array a[1:n] of elements in non-decreasing 3. //order,
n>=0,determine whether ‘x’ is present and
4. // if so, return ‘j’ such that x=a[j]; else return 0.
3
Page

5. {

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

6. low:=1; high:=n;
7. while (low<=high) do
8. {
9. mid:=[(low+high)/2];
10. if (x<a[mid]) then high; 11. else if(x>a[mid]) then
low=mid+1;

12. else return mid;

13. }
14. return 0;
15. }

• Algorithm, describes this binary search method, where Binsrch has 4I/ps a[], I , l &
x.
• It is initially invoked as Binsrch (a,1,n,x) • A non-recursive version of Binsrch is
given below.
• This Binsearch has 3 i/ps a,n, & x.

VTUPulse.com
•

•
The while loop continues processing as long as there are more elements left to
check.
At the conclusion of the procedure 0 is returned if x is not present, or ‘j’ is returned,
such that a[j]=x.
• We observe that low & high are integer Variables such that each time through the
loop either x is found or low is increased by at least one or high is decreased at least
one.

Thus we have 2 sequences of integers approaching each other and eventually low becomes
> than high & causes termination in a finite no. of steps if ‘x’ is not present.
Example:

1) Let us select the 14 entries.

-15,-6,0,7,9,23,54,82,101,112,125,131,142,151.

Place them in a[1:14], and simulate the steps Binsearch goes through as it searches for
different values of ‘x’.
4
Page

Only the variables, low, high & mid need to be traced as we simulate the algorithm.

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

We try the following values for x: 151, -14 and 9.for 2 successful searches & 1 unsuccessful
search.
• Table. Shows the traces of Bin search on these 3 steps.

X=151 low high mid

1 14 7
8 14 11
12 14 13
14 14 14
Found

x=-14 low high mid

1 14 7
1 6 3
12 1
22 2

VTUPulse.com
2 1 Not found

x=9 low high mid

1 14 7
1 6 3
4 6 5
Found
Theorem: Algorithm Binsearch(a,n,x) works correctly.

Proof:

We assume that all statements work as expected and that comparisons such as x>a[mid]
are appropriately carried out.

• Initially low =1, high= n,n>=0, and a[1]<=a[2]<=……..<=a[n].

5
Page

• If n=0, the while loop is not entered and is returned.

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

• Otherwise we observe that each time thro’ the loop the possible elements to be checked
of or equality with x and a[low], a[low+1],……..,a[mid],……a[high].
• If x=a[mid], then the algorithm terminates successfully.
• Otherwise, the range is narrowed by either increasing low to (mid+1) or decreasing
high to (mid-1).
• Clearly, this narrowing of the range does not affect the outcome of the search.
• If low becomes > than high, then ‘x’ is not present & hence the loop is exited.

Maximum and Minimum:

• Let us consider another simple problem that can be solved by the divide-and
conquer technique.
• The problem is to find the maximum and minimum items in a set of ‘n’ elements.
In analyzing the time complexity of this algorithm, we once again concentrate on the
no. of element comparisons.

• More importantly, when the elements in a[1:n] are polynomials, vectors, very large
numbers, or strings of character, the cost of an element comparison is much higher than
the cost of the other operations.

VTUPulse.com
•

1.
2.
Hence, the time is determined mainly by the total cost of the element comparison.

Algorithm straight MaxMin(a,n,max,min)

// set max to the maximum & min to the minimum of a[1:n]
3. {
4. max:=min:=a[1];
5. for I:=2 to n do
6. {
7. if(a[I]>max) then max:=a[I];
8. if(a[I]<min) then min:=a[I];
9. }

10. }
6

Algorithm: Straight forward Maximum & Minimum

Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

Straight MaxMin requires 2(n-1) element comparison in the best, average & worst cases.

• An immediate improvement is possible by realizing that the comparison a[I]<min

is necessary only when a[I]>max is false.
Hence we can replace the contents of the for loop by,
If(a[I]>max) then max:=a[I];

Else if (a[I]<min) then min:=a[I];

Now the best case occurs when the elements are in increasing order.

The no. of element comparison is (n-1).

• The worst case occurs when the elements are in decreasing order. The no. of
elements comparison is 2(n-1)

• The average no. of element comparison is < than 2(n-1)

• On the average a[I] is > than max half the time, and so, the avg. no. of comparison
is 3n/2-1.
• A divide- and conquer algorithm for this problem would proceed as follows:

VTUPulse.com
Let P=(n, a[I] ,……,a[j]) denote an arbitrary instance of the problem.

Here ‘n’ is the no. of elements in the list (a[I],….,a[j]) and we are interested in

finding the maximum and minimum of the list.

• If the list has more than 2 elements, P has to be divided into smaller instances.

• For example , we might divide ‘P’ into the 2 instances,

P1=([n/2],a[1],……..a[n/2]) & P2= (n-[n/2],a[[n/2]+1],…..,a[n])

• After having divided ‘P’ into 2 smaller sub problems, we can solve them by
recursively invoking the same divide-and-conquer algorithm.
7
Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

Algorithm: Recursively Finding the Maximum & Minimum

1. Algorithm MaxMin (I,j,max,min)

2. //a[1:n] is a global array, parameters I & j
3. //are integers, 1<=I<=j<=n.The effect is to 4. //set max & min to the largest &
smallest value
5. //in a[I:j], respectively.
6. {
7. if(I=j) then max:= min:= a[I];
8. else if (I=j-1) then // Another case of small(p)
9. {
10. if (a[I]<a[j]) then
11. {
12. max:=a[j];
13. min:=a[I];

VTUPulse.com
14. } else
15. {
16. max:=a[I];
17. min:=a[j];
18. }
19. }
20. else
21. {
22. // if P is not small, divide P into subproblems.
23. // find where to split the set mid:=[(I+j)/2];
24. //solve the subproblems
25. MaxMin(I,mid,max.min);
26. MaxMin(mid+1,j,max1,min1);
8

27. //combine the solution

Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

28. if (max<max1) then max=max1;
29. if(min>min1) then min = min1;
30. }
31. }

• The procedure is initially invoked by the statement,

MaxMin(1,n,x,y)
• Suppose we simulate MaxMin on the following 9 elements

A: [1] [2] [3] [4] [5] [6] [7] [8] [9]

22 13 -5 -8 15 60 17 31 47

• A good way of keeping track of recursive calls is to build a tree by adding a node
each time a new call is made.
• For this Algorithm, each node has 4 items of information: I, j, max & imin.
• Examining fig: we see that the root node contains 1 & 9 as the values of I &j
corresponding to the initial call to MaxMin.

VTUPulse.com
• This execution produces 2 new calls to MaxMin, where I & j have the values 1, 5
& 6, 9 respectively & thus split the set into 2 subsets of approximately the same
size.
• From the tree, we can immediately see the maximum depth of recursion is 4.
(including the 1st call)
• The include no.s in the upper left corner of each node represent the order in which
max & min are assigned values.

No. of element Comparison:

• If T(n) represents this no., then the resulting recurrence relations is

T(n)={ T([n/2]+T[n/2]+2 n>2

n=2

0 n=1
9
Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

When ‘n’ is a power of 2, n=2^k for some +ve integer ‘k’, then
T(n) = 2T(n/2) +2
= 2(2T(n/4)+2)+2
= 4T(n/4)+4+2
*

= 2^k-1T(2)+
= 2^k-1+2^k-2
= 2^k/2+2^k-2
= n/2+n-2
= (n+2n)/2)-2
T(n)=(3n/2)-2

*Note that (3n/3)-3 is the best-average, and worst-case no. of comparisons when ‘n’ is
a power of 2.

VTUPulse.com
MERGE SORT

• As another example divide-and-conquer, we investigate a sorting algorithm that has

the nice property that is the worst case its complexity is O(n log n)
• This algorithm is called merge sort
• We assume throughout that the elements are to be sorted in non-decreasing order.
• Given a sequence of ‘n’ elements a[1],…,a[n] the general idea is to imagine then
split into 2 sets a[1],…..,a[n/2] and a[[n/2]+1],….a[n].
• Each set is individually sorted, and the resulting sorted sequences are merged to
produce a single sorted sequence of ‘n’ elements.
• Thus, we have another ideal example of the divide-and-conquer strategy in which
the splitting is into 2 equal-sized sets & the combining operation is the merging of
2 sorted sets into one.
10
Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

Algorithm For Merge Sort:

1. Algorithm MergeSort(low,high)
2. //a[low:high] is a global array to be sorted
3. //Small(P) is true if there is only one element 4. //to sort. In this case the list is
already sorted.
5. {
6. if (low<high) then //if there are more than one element
7. {
8. //Divide P into subproblems
9. //find where to split the set
10. mid = [(low+high)/2]; 11. //solve the subproblems.
12. mergesort (low,mid);
13. mergesort(mid+1,high);

VTUPulse.com
14. //combine the solutions .
15. merge(low,mid,high);
16. }
17. }

Algorithm: Merging 2 sorted subarrays using auxiliary storage.

1. Algorithm merge(low,mid,high)
2. //a[low:high] is a global array containing
3. //two sorted subsets in a[low:mid]
4. //and in a[mid+1:high].The goal is to merge these 2 sets into
5. //a single set residing in a[low:high].b[] is an auxiliary global array.
6. {
11

7. h=low; I=low; j=mid+1;

Page

8. while ((h<=mid) and (j<=high)) do

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

9. {
10. if (a[h]<=a[j]) then
11. {
12. b[I]=a[h];
13. h = h+1;
14. }
15. else
16. {
17. b[I]= a[j];
18. j=j+1;
19. }
20. I=I+1;
21. }
22. if (h>mid) then
23. for k=j to high do

VTUPulse.com
24.
25.
26.
{
b[I]=a[k];
I=I+1;
27. }
28. else
29. for k=h to mid do
30. {
31. b[I]=a[k];
32. I=I+1;
33. }
34. for k=low to high do a[k] = b[k];
35. }
12

• Consider the array of 10 elements a[1:10] =(310, 285, 179, 652, 351, 423, 861, 254,
Page

450, 520)

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

• Algorithm Mergesort begins by splitting a[] into 2 sub arrays each of size five
(a[1:5] and a[6:10]).
• The elements in a[1:5] are then split into 2 sub arrays of size 3 (a[1:3] ) and 2(a[4:5])
• Then the items in a a[1:3] are split into sub arrays of size 2 a[1:2] & one(a[3:3])
• The 2 values in a[1:2} are split to find time into one-element sub arrays, and now
the merging begins.

(310| 285| 179| 652, 351| 423, 861, 254, 450, 520)

Where vertical bars indicate the boundaries of sub arrays.

Elements a[I] and a[2] are merged to yield,

(285, 310|179|652, 351| 423, 861, 254, 450, 520)

VTUPulse.com
Then a[3] is merged with a[1:2] and

(179, 285, 310| 652, 351| 423, 861, 254, 450, 520)

Next, elements a[4] & a[5] are merged.

(179, 285, 310| 351, 652 | 423, 861, 254, 450, 520)

And then a[1:3] & a[4:5]

(179, 285, 310, 351, 652| 423, 861, 254, 450, 520)

Repeated recursive calls are invoked producing the following sub arrays. (179,
285, 310, 351, 652| 423| 861| 254| 450, 520)
13

Elements a[6] &a[7] are merged.

Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

Then a[8] is merged with a[6:7]

(179, 285, 310, 351, 652| 254,423, 861| 450, 520)

Next a[9] &a[10] are merged, and then a[6:8] & a[9:10]
(179, 285, 310, 351, 652| 254, 423, 450, 520, 861 )

At this point there are 2 sorted sub arrays & the final merge produces the fully sorted
result.

(179, 254, 285, 310, 351, 423, 450, 520, 652, 861)

• If the time for the merging operations is proportional to ‘n’, then the computing time
for merge sort is described by the recurrence relation.

T(n) = { a
n=1,’a’ a constant

VTUPulse.com
2T(n/2)+cn
n>1,’c’ a constant.

14
Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

When ‘n’ is a power of 2, n= 2^k, we can solve this equation by successive substitution.

T(n) =2(2T(n/4) +cn/2) +cn

= 4T(n/4)+2cn
= 4(2T(n/8)+cn/4)+2cn
*

= 2^k T(1)+kCn.
= an + cn log n.

It is easy to see that if s^k<n<=2^k+1, then T(n)<=T(2^k+1). Therefore,

T(n)=O(n log n)

VTUPulse.com
QUICK SORT

• The divide-and-conquer approach can be used to arrive at an efficient sorting

method different from merge sort.

• In merge sort, the file a[1:n] was divided at its midpoint into sub arrays which were
independently sorted & later merged.
• In Quick sort, the division into 2 sub arrays is made so that the sorted sub arrays do
not need to be merged later.

• This is accomplished by rearranging the elements in a[1:n] such that a[I]<=a[j] for
all I between 1 & n and all j between (m+1) & n for some m, 1<=m<=n.

• Thus the elements in a[1:m] & a[m+1:n] can be independently sorted.

15

• No merge is needed. This rearranging is referred to as partitioning.

Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

• Function partition of Algorithm accomplishes an in-place partitioning of the
elements of a[m:p-1]

• It is assumed that a[p]>=a[m] and that a[m] is the partitioning element. If m=1 &
p-1=n, then a[n+1] must be defined and must be greater than or equal to all elements
in a[1:n]

• The assumption that a[m] is the partition element is merely for convenience, other
choices for the partitioning element than the first item in the set are better in practice.

• The function interchange (a,I,j) exchanges a[I] with a[j].

Algorithm: Partition the array a[m:p-1] about a[m]

1. Algorithm Partition(a,m,p)
2. //within a[m],a[m+1],…..,a[p-1] the elements
3. // are rearranged in such a manner that if
4. //initially t=a[m],then after completion

VTUPulse.com
5. //a[q]=t for some q between m and
6. //p-1,a[k]<=t for m<=k<q, and 7. //a[k]>=t for q<k<p. q is returned
8. //Set a[p]=infinite.
9. {
10. v=a[m];I=m;j=p;
11. repeat
12. {
13. repeat
14. I=I+1;
15. until(a[I]>=v);
16. repeat
17. j=j-1;
16

18. until(a[j]<=v);
Page

19. if (I<j) then interchange(a,i.j);

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

20. }until(I>=j);
21. a[m]=a[j]; a[j]=v;
22. retun j;
23. }

1. Algorithm Interchange(a,I,j)
2. //Exchange a[I] with a[j]
3. {
4. p=a[I];
5. a[I]=a[j];
6. a[j]=p;
7. }

Algorithm: Sorting by Partitioning

VTUPulse.com
1. Algorithm Quicksort(p,q)
2. //Sort the elements a[p],….a[q] which resides
3. //is the global array a[1:n] into ascending
4. //order; a[n+1] is considered to be defined
5. // and must be >= all the elements in a[1:n]
6. {
7. if(p<q) then // If there are more than one element
8. {
9. // divide p into 2 subproblems
10. j=partition(a,p,q+1);
11. //’j’ is the position of the partitioning element.
12. //solve the subproblems.
13. quicksort(p,j-1);
17

14. quicksort(j+1,q);
Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

15. //There is no need for combining solution.
16. }
17. }

STRASSON’S MATRIX MULTIPLICAION

• Let A and B be the 2 n*n Matrix. The product matrix C=AB is calculated by using
the formula,

C (i ,j )= A(i,k) B(k,j) for all ‘i’ and and j between 1 and n.

• The time complexity for the matrix Multiplication is O(n^3).

• Divide and conquer method suggest another way to compute the product of n*n
matrix.

• We assume that N is a power of 2 .In the case N is not a power of 2 ,then enough

VTUPulse.com
rows and columns of zero can be added to both A and B .SO that the resulting
dimension are the powers of two.
• If n=2 then the following formula as a computed using a matrix multiplication
operation for the elements of A & B.

• If n>2,Then the elements are partitioned into sub matrix n/2*n/2..since ‘n’ is a
power of 2 these product can be recursively computed using the same formula .This
Algorithm will continue applying itself to smaller sub matrix until
‘N” become suitable small(n=2) so that the product is computed directly .

• The formula are

A11 A12 B11 B12 C11 C12

* =
18

A21 A21 B21 B22 C21 C22

Page

2019-20
`
Module-2 Design and Analysis of Algorithm

DIVIDE AND CONQUER

C11 = A11 B11 + A12 B21

C12 = A11 B12 + A12 B22

C21 = A21 B11 + A22 B21

C22 = A21 B12 + A22 B22

• To compute AB using the equation we need to perform 8 multiplication of n/2*n/2
matrix and from 4 addition of n/2*n/2 matrix.
• Ci,j are computed using the formula in equation 4

• As can be sum P, Q, R, S, T, U, and V can be computed using 7 Matrix

multiplication and 10 addition or subtraction.
• The Cij are required addition 8 addition or subtraction.

VTUPulse.com
19
Page

2019-20
 DIVIDE AND CONQUER
`
Module-2 Design and Analysis of Algorithm

Finally we get T(n) =O( n ^log27)

Example

44 4 4
*
44 4 4

P=(4*4)+(4+4)=64

Q=(4+4)4=32

R=4(4-4)=0

VTUPulse.com
S=4(4-4)=0

T=(4+4)4=32

U=(4-4)(4+4)=0

V=(4-4)(4+4)=0

C11=(64+0-32+0)=32

C12=0+32=32

C21=32+0=32

C22=64+0-32+0=32
20

So the answer c(i,j) is 32 32

Page

32 3

2019-20
 DIVIDE AND CONQUER
`
Module-2 Design and Analysis of Algorithm
since n/2n/2 &matrix can be can be added in Cn for some constant C, The overall computing
time T(n) of the resulting divide and conquer algorithm is given by the sequence.
T(n)= b n<=2 a &b are
8T(n/2)+cn^2 n>2 constant

That is T(n)=O(n^3)

* Matrix multiplication are more expensive then the matrix addition O(n^3).We can
attempt to reformulate the equation for Cij so as to have fewer multiplication and possibly
more addition .

• Stressen has discovered a way to compute the Cij of equation (2) using only 7
multiplication and 18 addition or subtraction.
• Strassen’s formula are

P= (A11+A12)(B11+B22)

VTUPulse.com
Q= (A12+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

C!2=R+t

C21=Q+T
C22=P+R-Q
21
Page

2019-20