Divide and Conquer Algorithm

Divide and Conquer Algorithm

Divide and Conquer algorithm consists  following three steps.

1. Divide: Divide is the the original problem into a subproblems using recursion.
2. Conquer: Conquer is to solve every smaller subproblem individually, recursively.
3. Combine: Combine is the solutions of the subproblems to get the solution to the actual problem.

 

Examples of Divide and conquer

The computer algorithms are based on divide-and-conquer programming approach they are follows−

• Merge Sort
• Quick Sort
• Binary Search
• Strassen’s Matrix Multiplication
• Closest pair (points)

 

Example :

Divide And Conquer algorithm

DC(a, i, j) 
{ 
 if(small(a, i, j))
 return(Solution(a, i, j))
 else m = divide(a, i, j)     // f1
 (n) b = DC(a, i, mid)        // T(n/2) 
 c = DC(a, mid+1, j)         // T(n/2) 
 d = combine(b, c)          // f2
 (n) return(d) 
}

 

Program for Divide and Conquer in C

#include <stdio.h>
int DAC_Max(int a[], int index, int l);
int DAC_Min(int a[], int index, int l);
 
// function to find the largest no. in a given array.
int DC_Max(int a[], int index, int l)
{
    int max;
    if (index >= l - 2) {
        if (a[index] > a[index + 1])
            return a[index];
        else
            return a[index + 1];
    }
 
    // find the largest element 
    max = DC_Max(a, index + 1, l);
 
    if (a[index] > max)
        return a[index];
    else
        return max;
}
 
// Function to find the smallest no.
int DC_Min(int a[], int index, int l)
{
    int min;
    if (index >= l - 2) {
        if (a[index] < a[index + 1])
            return a[index];
        else
            return a[index + 1];
    }
 
    // find the Samllest element 
    min = DC_Min(a, index + 1, l);
 
    if (a[index] < min)
        return a[index];
    else
        return min;
}
 
//Code
int main()
{
    // Defining the variables
    int min, max, N;
 
    // Initializing the array
    int a[7] = { 75, 260, 60, 95, 150, 15, 10 };
 
    // recursion 
    max = DC_Max(a, 0, 7);
 
    // recursion 
    min = DC_Min(a, 0, 7);
    printf(" smallest no is : %d\n", min);
    printf(" largest no is : %d", max);
    return 0;
}

Output

samllest no is: 10
lasgest no is: 260

 

Program for Divide and Conquer in C++

# include<iostream>
using namespace std;
 
// find the largest no.

int DC_Max(int arr[], int index, int l)
{
    int max;
    if(index >= l - 2)
    {
        if(arr[index] > arr[index + 1])
          return arr[index];
        else
          return arr[index + 1];
    } 
    max = DC_Max(arr, index + 1, l);   
    if(arr[index] > max)
       return arr[index];
    else
       return max;
}
 
// find the smallest no. 
int DC_Min(int arr[], int index, int l)
{
    int min;
    if(index >= l - 2)
    {
        if(arr[index] < arr[index + 1])
          return arr[index];
        else
          return arr[index + 1];
    }
     
    min = DC_Min(arr, index + 1, l);  
    if(arr[index] < min)
       return arr[index];
    else
       return min;
}
 
//  code
int main()
{
    int arr[] = {130, 41, 45, 32, 58, 9, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max, min;
    max = DC_Max(arr, 0, n);
    min = DC_Min(arr, 0, n);
    cout << "largest: " << max << endl;
    cout << "smallest: " << min << endl;
    return 0;
}

Output

Largest: 130
Smallest: 9

Program for Divide and Conquer in Java

class ABC{
 
// find the largest no. 
static int DC_Max(int a[], int index, int l)
{
    int max;
     
    if (index >= l - 2)
    {
        if (a[index] > a[index + 1])
            return a[index];
        else
            return a[index + 1];
    }
 
    // How to find the Maximum element 
    max = DAC_Max(a, index + 1, l);
 
    if (a[index] > max)
        return a[index];
    else
        return max;

/  find the samllest no
static int DAC_Min(int a[], int index, int l)
{
    int min;
    if (index >= l - 2)
    {
        if (a[index] < a[index + 1])
            return a[index];
        else
            return a[index + 1];
    }
 
    // find the samllest element in the given array.
    min = DC_Min(a, index + 1, l);
 
    if (a[index] < min)
        return a[index];
    else
        return min;
}
 
//  Code
public static void main(String[] args)
{
     
    // Defining the variables
    int min, max;
 
    // Initializing the array
    int a[] = { 70, 250, 50, 80, 140, 12, 14 };
 
    // Recursion 
    max = DC_Max(a, 0, 7);
 
    // Recursion 
    min = DC_Min(a, 0, 7);
     
    System.out.printf("The smallest number in " +
                      "a given array is : %d\n", min);
    System.out.printf("The largest number in " +
                      "a given array is : %d", max);
}
}
}

Output

Samllest: 14
Largest: 250

 

 

Applications of Divide and Conquer Approach:

Based on the concept of the Divide and Conquer Technique they are follows

1. Binary Search
2. Quicksort
3. Merge Sort
4. Closest Pair of Points
5. Strassen’s Algorithm
6. Cooley-Tukey Fast Fourier Transform (FFT) algorithm
7. Karatsuba algorithm for fast multiplication

 

Advantages of Divide and Conquer

• It is using for Solving difficult problems
• Divide and conquer is used for Parallelism that is  to solve the subprblems independently
• It is used to Memory access i.e. it make efficient use of memory caches

Disadvantages of Divide and Conquer

• Divide and conquer approach is that recursion is slow
• Problem decomposition may be very complex and so it not suitable to divide and conquer.
• An explicit stack  overuse the space.

 

Also read, Master theorem