Divide & Conquer

hello Everyone !!

Welcome back to the “Shelf of Algorithm”. Today we will cover Divide and Conquer method , type of algorithm . This type is one of the interesting and simple one ,so I hope you all will get clear easily then Let’s go . . . .

Divide and Conquer method is . . . I think the method name define itself only i.e. We have to break problem into small sub problems ,sub instances and the solution of these sub problems get combined in single solution.

Defination:

Divide and conquer is a strategy in which it suggests to split the input into distinct sub problems, which have compulsion  of same type as the original problem,and must be found to combine sub-solution into one whole solution.

This algorithm is solved with simple three steps as follows:

1. Divide: Split the original problem into sub problem.
2. Conquer: Recursively solve these sub problems.
3. Combine: Appropriately combine the answers.

Suppose given function to determine on n inputs this algorithm gives an idea to split this n inputs into k distinct subsets .

 1  < K <=  n; Where K is sub problems of the original problem, n is the original problem.

Example :  Algorithm for divide and conquer

1. Algorithm DAndC( P )
2. {
3.      If Small( P ) then return S( P );
4.      Else 
5.      {
6.             Divide P into smaller instances P1,  P2, P3, P4, . . . ,Pk , k >= 1;
7.             Apply DAndC to each of these sub problems;
8.           Return Combine( DAndC( p1 ), DAndC( p2 ), DAndC( p3 ), . . ,DAndC( pk ) );
9.      }
10. }

Step 1: check whether the given problem is smallest or not (i.e. whether it contains single element).

• DAndC  is initially invoked as DAndC(P), where P is the problem to solve.
• Small(P) is Boolean valued function  which determine the the function have small size or not .
• If true : i.e. Given problem conatins single element then
  • {
  • it will show output directly and we havn’t need to split it.
  • }

Step 2: If problem contain more than one element then divide given problem.

• {
• the problem P  is get split into distinct sub problems . 
•  [ p1, p2 , p3 , . . . . . . pk] .
• Then sub problems P1,  P2, P3, P4, . . .  ,Pk are solved by the above algorithm.
• }

Step 3: Apply D&C to all sub problems or sub instances and combine in single solution.

• apply D&C to all sub problems i.e.
• D&C( P1) , D&C( P2) ,D&C( P3) , . . . . . . D&C( Pk).
• combine the all solution in single
• combine( D&C( P1) , D&C( P2) ,D&C( P3) , . . . . . . D&C( Pk) ).

Examples :

• Binary Search.
• Max-Min by D&C.
• Merge Sort.
• Quick Sort.
• Selection sort.

I think examples are the fastest method to understand the concept quickly and clearly. I’ll cover one example in brief , so let’s go for Binary search.

Binary search :

The simple logic of binary search is calculate the mid of element list and compare with search element i.e. search key if element is smaller than mid then replace the high with mid-1 if it is greater than the mid then replace low with mid+1 . We will go with algorithm. . .

• Algorithm BinSrch( a , i , l , x ) // x is the element to be searched
• {
  • if ( l = i) then // problem size is small or not
  • {
    • if ( x = a[i] )
      • then return i ;
    • else return 0 ;
  • }
  • else
  • { //break problem into subproblems
    • mid = (i+2) / 2 ;
    • if (x = a[mid]) then return mid //mid is the search element
    • else if( x < a[mid] )
      • return BinSrch( a , i , mid-1 , x )
    • else
      • return BinSrch( a , mid+1 , l , x )
  • }
• }

Difficult to understand ? ? Let’s consider one exapmle of 14 entries :

-15 , -6 , 0 , 7 , 9 , 23 , 54 , 82 , 101 , 112 , 125 , 131 , 142 , 151

So we have to find out the 151, -14, &9 to search this element we will follow our algorithm so first element ,search key is 151 .

Step 1:

Our element list is large in size so instead of going in if statement we will directly go through the else body .We have calculate the mid of list.

i = 14. //we have 14 element in our list mid = i / 2 // mid = 14 / 2 = 7.

Step 2 :

Check the search key is equal to the value in the mid position. So check … X = a[ mid ]. // Check 151 = a[7]

So we have a[7] = 54 which is not equal to the search key.

Step 3:

Check if x is less than a[7] i.e. check 151 is less than 54 so no it will go to the next else statment and replace the i with mid+1 .Now we have to search between a[8] to a[14] .

Again it will calculate the mid and it will give the value 112 which is again smaller than search key so replace i with mid+1 .after two iteration we will find out our search key i.e. 151 at the location of a[14].

Remaining search keys are -14 and 9 so -14 will not get found as the low get larger than high it will terminate and print that element is not present.

Hope you all get clear about the divide and conquer concept. So let me know if you have any doubt or any questions in comment section given below . Till then stay tuned stay connected to know about the next type. I’ll come back with next blog and next type.

Thank you…