Skip to main content

What is Divide And Conquer Technique

Divide and Conquer is a programming technique which makes the program more efficient to write. And this technique work on the concept of recursion to solve a problem step by step. Generally this technique work in three parts:- Divide:-  Divide the problem into some subproblem. Conquer:-  Conquer the subproblem by calling recursively until subproblem solved. Combine:-  (Optional Step) Combine the subproblem solution. So, that we will get the final problem Solution.  When the subproblems are large enough to solve recursively, we call the recursive case. Once the subproblem becomes small enough that we no longer recursive, we say that the recursion "bottom out" and that we have gotten down to the base case.                          Application of Divide and Conquer Quick Sort Strassen's algorithm for matrix multiplication Merge Sort Counting inversions Binary Search Finding Min and ...
1 comment

What is Divide And Conquer Technique

Divide and Conquer is a programming technique which makes the program more efficient to write.
And this technique work on the concept of recursion to solve a problem step by step.
Generally this technique work in three parts:-
  1. Divide:- Divide the problem into some subproblem.
  2. Conquer:- Conquer the subproblem by calling recursively until subproblem solved.
  3. Combine:- (Optional Step) Combine the subproblem solution. So, that we will get the final problem Solution. 
When the subproblems are large enough to solve recursively, we call the recursive case. Once the subproblem becomes small enough that we no longer recursive, we say that the recursion "bottom out" and that we have gotten down to the base case.
                        

Application of Divide and Conquer

  1. Quick Sort
  2. Strassen's algorithm for matrix multiplication
  3. Merge Sort
  4. Counting inversions
  5. Binary Search
  6. Finding Min and max

Divide and Conquer Abstract Algorithm

DAC(a,i,j)
{        
          //small(a,i,j) represent the smallest subproblem which can't be further divided
          if(small(a,i,j))  
                //solution(a,i,j) return some constant value
               return(solution(a,i,j));
           else
            {
                 //Divide(a,i,j) represent the dividing of large problem into small
                 mid=Divide(a,i,j);
                 b=DAC(a,i,mid);
                 c=DAC(a,mid+1,j);
                 //combine(b,c) represnt merging up of small subproblem
                 d=combine(b,c);
                  return d;
              }
}
                            

About Complexity of Abstract Divide & Conquer Algorithm

small(a,i,j)            having O(1) time complexity
solution(a,i,j)        having O(1) time complexity
Divide(a,i,j)          having some constant C1 time complexity
b=DAC(a,i,mid);  having T(n/2) time complexity
c=DAC(a,i,mid);  also having T(n/2) time complexity
combine(b,c)         having some constant C2 time complexity

The total time complexity of Divide and Conquer
      T(n)=O(1)   if n is small
      T(n)=C1+T(n/2)+T(n/2)+C2   if n is large

assuming C=C1+C2
Then,
         T(n)=2T(n/2)+C     //for two equal subproblem cost

And for 'a' equal subproblem of size 'b'
           T(n)=aT(n/b)+C     //It also depict that Divide and Conquer can be solved by Master's Theorem

Important Points about Divide & Conquer

  1. Function calling occur in Preorder
  2. Execution of function happen in Postorder














Comments

Post a Comment

Popular posts from this blog

Sorting numbers using LinkList in C Language

#include<stdio.h> #include<conio.h> //creating  a structure for linked list typedef struct node {     int data;     struct node* next; }node;     //rename whole structure // function for creating nodes of linked list node * createlinkedlist(int n); //return address void display(node * head); void sort1(node * head,int n); int main(){ int n=0; node* HEAD=NULL; node* HEAD1=NULL; printf("how many nodes want to add in a linklist "); scanf("%d",&n); HEAD=createlinkedlist(n); sort1(HEAD,n); display(HEAD); return 0; } node * createlinkedlist(int n) {     int i=0;     node * head=NULL;     node * temp=NULL;     node * p=NULL;     for(i=0;i<n;i++)     {         //creating unattached node         temp=(node*)malloc(sizeof(node));       ...
Post a Comment
Read more

POLYGON FORMATION IN C

                       /*  POLYGON FORMATION IN C  */ #include<stdio.h> #include<conio.h> #include<graphics.h> #include<stdlib.h> void main() {     int n,x[15],y[15],i;     printf("ENTER THE NUMBER OF SIDE OF POLYGON:\n");     scanf("%d",&n);     if(n<3)     { printf("POLYGON CAN'T BE FORM\n"); getch(); exit(0);     }     else     { for(i=1;i<=n;i++) { printf("ENTER THE CORDINATES OF THE POLYGON %d SIDE\n",i); scanf("%d %d",&x[i],&y[i]); } int gd=DETECT,gm; initgraph(&gd,&gm,"C:\\tc\\BGI"); for(i=1;i<n;i++) { line(x[i],y[i],x[i+1],y[i+1]); } line(x[1],y[1],x[n],y[n]); } getch(); }
1 comment
Read more