Design and Analysis of Algorithms - Old Questions

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)