Thursday, June 13, 2019

Divide and conquer in design and analysis of algorithm

Divide and conquer methods.

   The divide and conquer methods are used in designing algorithms when the function to be computed has n inputs.
   As the title of this methods indicates, the original problem of n inputs is divided, recursively by reapplication of the divide and conquer principle,
   into m subproblems for 1<=m<=n till it becomes easy to solve each of these m subproblems individually.
    The divide and conquer paradigm consists of the following three steps at each level of recursion.
      1. Divide the problem into a number of subproblems,
      2.Conquer the subproblems by solving them and 
      3. Combine the solutions of all the subproblems to obtain a solution for the original problem.

Binary Search:

We are given a sorted array a[1: n] of size n and a search element x. The problem is to determine whether x is present in the list a[] or not.If it is present
, we determine a value j such that a[j]=x, 1<=j<=n. If x is not present in the list, then proper action will be taken, maybe one can set conveniently, j=0.

The divide and conquer method is called a binary search method if m is chosen every time such that am is the middle element of the list, i.e., m=[(n+1)/2].

Now we represent recursive and iterative algorithms.

Algorithm 1. Recursive binary search.

1.Algorithm BinRSearch (a, j, x)
2.   //a[j, k] is a given sorted array of non-decreasing elements.
3.   //order, 1<=j<=k. This algorithm searches the list for the
4.   //presence of x. If the search is successful, i.e. if x is 
5.   //present, it returns i such that x=a[i], else returns zero.
6.    {
7.        if (k=j) then // small(P)
8.              {
9.                  if (x=a[j] ) then return j;
10.                     else return 0;
11.              }
12.                else
13.                {//p is divide into smaller subproblems.
14.               mid:=[(j+k)/2]
15.                     if ( x=a [mid]) then return mid;
16.                         else if ( x<a[mid]) then
17.                             return BinRSearch (a, j, mid-1,x);
18.                                else return BinRSearch (a, mid+1,k,x);
19.            }
20.       }

Algorithm 2. Iterative binary search

1.Algorithm ItBinsearch(a, n, x)
2. //a[1:n] is an array of n element in non decreasing
3.  //order. This algorithm determines whether x is present in
4. //a[] and if so returns i such that x =a[i ], else returns 0
5. {
6.   1:=1;h:=n;
7.   while (1 d'' hi ) do
8.              {
9.                  mid:=[(1+ h)/2];
10.                    if (x> a[mid]) then
11.                     h:=mid-1;
12.                    else if (x>a[mid]) then
13.                             1:=mid+1;
14.                           else return mid;
15.                }
16.           return 0;
17.   }

Algorithm3. Merge sort

1.Algorithm MergeSort (i,  j)
2.  // a[i, j] is an unsorted array.
3.   //small(p) is true if p can be solved directly.
4.   {
5.         if (i<j) then //s(p) is false
6.            {
7.            //Divide p into smaller sub problems 
8.          mid:=[(i+j)]
9.            MergeSort(i, mid);
10.           MergeSort (mid+1,j);
11.          //Combine the sub soultions
12.              Merge(i, j, mid);
13.           }
14.   }

No comments:

Post a Comment