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 = 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^{2} entries, each of which multiples n pairs
- Z_{ij}=∑X_{ik}Y_{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^{2})
- Θ(1) time to partition matrices
- 8 Multiplications of arrays of size n/2n/2
- Θ(n^{2}) time to add n×n matrices
- T(n)= Θ(n^{3}) 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^{2}) 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)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 | Θ (n^{2}) | Θ (n^{2}) | Θ (n^{2}) |
Insertion sort | Θ (n^{2}) | Θ (n) | Θ (n^{2}) |
Merge sort | Θ (n log n) | Θ (n log n) | Θ (n log n) |
Quicksort | Θ (n^{2}) | Θ (n log n) | Θ (n log n) |
Strassen’s Matrix Multiplication | Θ(n^{2.81}) | Θ(n^{2.81}) | Θ(n^{2.81}) |
Matrix Multiplication | Θ(n^{2.38}) | Θ(n^{2.38}) | Θ(n^{2.38}) |
Integer Multiplication | Θ(n^{1.585}) | Θ(n^{1.585}) | Θ(n^{1.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:
Comments
write a commentPrashant DubeyApr 6, 2017
Tanuj PandeyJul 29, 2017
Deepali JoshiJul 29, 2017
Abhijit MajumdarJul 30, 2017
Bhoomi PrajapatiAug 1, 2017
Vishal UpadhayayAug 1, 2017
Arun KaranApr 17, 2019
how to fix connections to bluetooth audio devices and wireless displays in windows 10 and access the all setting of device.
Raghav SharmaSep 7, 2019
Malla DeepikaDec 28, 2019
Khushboo KinnerAug 6, 2020
This comment is hidden because it was marked spam.