Divide and Conquer Algorithm Study Notes

• Merge sort
• Quicksort
• Binary search
• Multiplication of large integers
• Matrix multiplication: Strassen’s algorithm
• Closest-pair algorithms

Divide & Conquer Algorithms can be solved using the master theorem to find the performance of algorithms.

Maximum and Minimum:

MaxMin(i, j, max, min)

{

if (i=j) then max := min := a[i];

else if (i=j-1) then

{

if (a[i] < a[j]) then max := a[j]; min := a[i];

else max := a[i]; min := a[j];

}

else

{

mid := ( i + j )/2;

// Solve the sub-problems.

MaxMin( i, mid, max, min );

MaxMin( mid+1, j, max1, min1 );

// Combine the solutions.

if (max < max1) then max := max1;

if (min > min1) then min := min1;

}

}

Time Complexity:

T(n) = 0; if n=1

= 1; if n=2

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

When n is a power of two, n = 2^k, for some positive integer k, then

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

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

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

…

= 2^k-1 T(2) + ∑(1≤i≤k-1) 2^k

= 2^{k-1 +} 2^k – 2

= 3n/2 – 2 = O(n)

Matrix Multiplication:

Simple approach of multiplication:

The product of two n × n matrices X and Y is a third n × n matrix Z = XY , with (i, j)th entry:

• Input: X, Y: Array(1 … n) of number
• Output: Z: Array(1 … n) := X x Y
• Obvious algorithm: Z has n² entries, each of which multiples n pairs
• Z_ij=∑X_ikY_kj
• Break X into X11, X12, X21, X22
• Break Y into Y11, Y12, Y21, Y22
• Break Z into Z11, Z12, Z21, Z22

• Let Z = product of two n/2 by n/2 arrays

Z11=X11×Y11+X12×Y21
Z12=X11×Y12+X12×Y22
Z21=X21×Y11+X22×Y21
Z22=X21×Y12+X22×Y22

• T(n)=Θ(1)+8T(n/2)+Θ(n²)
• Θ(1) time to partition matrices
• 8 Multiplications of arrays of size n/2n/2
• Θ(n²) time to add n×n matrices
• T(n)= Θ(n³) by master method

Strassen’s Algorithm:

Matrix multiplication is particularly easy to break into subproblems, because it can be performed block wise. Here divide X into four n/2 × n/2 blocks, and also Y:

Therefore, the product of X and Y is as follows:

• Uses 7 rather than 8 multiplications of n/2 by n/2 arrays
• Has more additions and subtractions of n/2 by n/2 arrays

• T(n)=7T(n/2)+Θ(n²) if n>1

• Solution (by Master Method): T(n)=Θ(n ^{log 7}) =Θ(n^2.81)
• Note: There are other matrix multiplication algorithms which can run even faster with T(n)=O(n^2.38)

Maximal Subarray:

Divide and conquer approach to find the maximal subarray:

maxsub(int[] S; low, high: int)

if low = high then return (low, high, S(low)); // return (lowIndex, highIndex, sum)

else mid = (low + high) / 2 ;

(llow, lhigh, lsum) = maxsub(S, low, mid) ;

(rlow, rhigh, rsum) = maxsub(S, mid+1, high) ;

(mlow, mhigh, msum) = middlemaxsub(S, low, mid, high) ;

end if;

return triple with highest sum

end maxsub

 

middlemaxsub(int[] S; low, high, int) return (lowIndex, highIndex, sum)

start at mid and find bestleft and leftsum

start at mid and find bestright and rightsum

return (bestleft, bestright, rightsum+leftsum)

end middlemaxsub

Closest Pair Algorithm:

Input: P = {p(1), p(2) ,…, p(n)} where p(i) = ( x(i), y(i) ). A set of n points in the plane.

Output: The distance between the two points that are closest.

Note: The distance DELTA( i, j ) between p(i) and p(j) is defined by the expression:

Square root of { (x(i)-x(j))² + (y(i)-y(j))² }

float function closest_pair (P: point set; n: integer )

float DELTA-LEFT, DELTA-RIGHT;

float DELTA;

begin

if n = 2 then

return distance from p(1) to p(2);

else

P-LEFT := ( p(1), p(2) ,…, p(n/2) );

P-RIGHT := ( p(n/2+1), p(n/2+2) ,…, p(n) );

DELTA-LEFT := closestpair( P-LEFT, n/2 );

DELTA-RIGHT := closestpair( P-RIGHT, n/2 );

DELTA := minimum ( DELTA-LEFT, DELTA-RIGHT );

/* Determine whether there are points p(l) in P-LEFT and p(r) in P-RIGHT with

distance( p(l), p(r) ) < DELTA. If there are such points, set DELTA to be the smallest

distance.*/

return DELTA;

end if;

end closest_pair;

The section between the two comment lines is the `combine’ stage of the Divide-and-Conquer algorithm.

If there are points p(l) and p(r) whose distance apart is less than DELTA then it must be the case that

• The x-coordinates of p(l) and p(r) differ by at most DELTA.
• The y-coordinates of p(l) and p(r) differ by at most DELTA.

Integer Multiplication:

Multiplying two n-bit integers algorithm using divide and conquer approach is given below:

Summary:

Algorithm	Worst-case running time	Best-case running time	Average-case running time
Selection sort	Θ (n2)	Θ (n2)	Θ (n2)
Insertion sort	Θ (n2)	Θ (n)	Θ (n2)
Merge sort	Θ (n log n)	Θ (n log n)	Θ (n log n)
Quicksort	Θ (n2)	Θ (n log n)	Θ (n log n)
Strassen’s Matrix Multiplication	Θ(n2.81)	Θ(n2.81)	Θ(n2.81)
Matrix Multiplication	Θ(n2.38)	Θ(n2.38)	Θ(n2.38)
Integer Multiplication	Θ(n1.585)	Θ(n1.585)	Θ(n1.585)
Closest Pair	Θ (n log n)	Θ (n log n)	Θ (n log n)
Binary Search	Θ(log n)	Θ(log n)	Θ(log n)
Maximum and Minimum	Θ(n)	Θ(n)	Θ(n)

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU’S Exam Prep Test Series check the following link: