Design and Analysis of Algorithms - Old Questions
2. Explain about divide and conquer paradigm for algorithm design with suitable example. Write the Quick sort algorithm using randomized approach and explain its time complexity. (4+6)
In divide and conquer paradigm, a problem is divided into smaller problems, then the smaller problems are solved independently, and finally the solutions of smaller problems are combined into a solution for the large problem.
Generally, divide-and-conquer algorithms have three parts:
- Divide: Divide the given problem into sub-problems using recursion.
- Conquer: Solve the smaller sub-problems recursively. If the subproblem is small enough, then solve it directly.
- Combine: Combine the solutions of the sub-problems that are part of the recursive process to solve the actual problem.
Example: Some problems which are based on the Divide & Conquer approach are:
- Binary Search
- Sorting (merge sort, quick sort)
Quick sort algorithm using randomized approach
RandQuickSort(A, l, r)
{
if(l<r)
{
m = RandPartition(A, l, r);
RandQuickSort(A, l, m-1);
RandQuickSort(A, m+1, r);
}
}
RandPartition(A, l, r)
{
k = random(l, r); //generates random number between i and j including both.
swap(A[l], A[k]);
return Partition(A, l, r);
}
Partition(A,l,r)
{
x =l; y =r ; p = A[l];
while(x<y)
{
do {
x++;
}while(A[x] <= p);
do {
y--;
} while(A[y] >=p);
if(x<y)
swap(A[x],A[y]);
}
A[l] = A[y]; A[y] = p;
return y; //return position of pivot
}
Time Complexity:
- Worst Case: T(n) = O(n2)
- Average Case: T(n) = O(nlogn)