Divide and Conquer Algorithm Study Notes

By Mukesh Kumar|Updated : December 12th, 2021

Divide and Conquer Design Technique

Divides the problem into smaller but similar subproblems (divide), solve it (conquer), and (combine) these solutions to create a solution to the original problem.

• Divide: Breaking the problem into several sub-problems that are similar to the original problem but smaller in size,
• Conquer: Solve the sub-problem recursively (successively and independently). If the subproblems are small enough, solve them in brute force fashion.
• Combine: Combine these solutions to sub-problems to create a solution to the original problem.

Divide & Conquer Algorithms:

• 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 = 2k, for some positive integer k, then

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

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

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

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

= 2k-1 + 2k – 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 n2 entries, each of which multiples n pairs
• Zij=∑XikYkj
• 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)+Θ(n2)
• Θ(1) time to partition matrices
• 8 Multiplications of arrays of size n/2n/2
• Θ(n2) time to add n×n matrices
• T(n)= Θ(n3) 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)+Θ(n2) if n>1
• Solution (by Master Method): T(n)=Θ(n log 7) =Θ(n2.81)
• Note: There are other matrix multiplication algorithms which can run even faster with T(n)=O(n2.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))2 + (y(i)-y(j))2 }

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:

Thanks

#DreamStriveSucceed

Posted by: Member since Feb 2020

write a comment Prashant DubeyApr 6, 2017

i think the best case tc of bubble sort is O(n) because when there is already sorted list is present it perform only one step in O(n) time Raghav SharmaSep 7, 2019

Is there any link where i can get some good quality notes for gate CS all subjects. Thanks in advance.   GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com