DAA- Divide and Conquer 

Divide and Conquer 

What is Divide and Conquer?

In the divide and conquer approach, firstly a problem is divided into smaller problems, then these smaller problems are solved independently, and then finally the solutions of these smaller problems are combined or merged in order to get a solution for the large or the main problem. 

The divide and Conquer algorithm can be divided into the following three steps.

Divide: Divide the original problem into a set of smaller problems or subproblems.

Conquer: Solve every subproblem individually and repeat it i.e., recursively.

Combine: Here, we put together or merge the solutions of the subproblems in order to get the solution for the whole problem.

Examples of the Divide and Conquer approach:

1. Maximum and Minimum Problem
2. Binary Search
3. Sorting (merge sort, quick sort)
4. Tower of Hanoi.

Fundamentals of the Divide and Conquer Strategy:

There are two fundamentals of the Divide and Conquer Strategy. Let us a look at them.

1. Relational Formula
2. Stopping Condition

1. Relational Formula: Relational formula is something that we generate from the given technique. Once the formula is generated, we apply the Divide and Conquer Strategy, i.e., we break the problem recursively and solve the subproblems that are broken.
2. Stopping Condition: Whenever we break the problem using the Divide and Conquer approach, we must have an idea of how much time we require in order to apply the strategy of Divide and Conquer. So, wherever the condition to stop our recursion of Divide and Conquer occurs, that condition is called a Stopping Condition.

Advantages of Divide and Conquer

• With the help of the Divide and Conquer strategy, it becomes easy for us to solve the biggest problems. One such problem is the Tower of Hanoi problem which is a complex mathematical puzzle. It is challenging to solve complicated problems of which you do not have a basic idea. But with the help of the divide and conquer approach, we can lessen the effort that it used to take as it works mainly on dividing the problem into two halves and then solving them recursively. The divide and Conquer algorithm is quicker than the other algorithms.
• The cache memory is efficiently used by the strategy as it does not occupy much of the space and it solves simple subproblems within the cache memory rather than accessing the slower main memory.
• It is much more proficient than the Brute Force technique which is its counterpart.
• These are the algorithms that inhibit parallelism. Hence, there is no need for any modification and it is also handled by the systems that incorporate parallel processing.

Disadvantages of Divide and Conquer

• As most of its algorithms are designed by incorporating recursion, it might require high memory management for proper functioning.
• An explicit stack might lead to overusing the space.
• Also, there is a chance for the system to crash if the recursion is performed continuously i.e if it exceeds the limit of the stack present in the CPU.

Applications of Divide and Conquer:

Binary Search 

The binary search algorithm is a searching algorithm which is also known as the half-interval search or logarithmic search algorithm.

QuickSort

It is the most efficient sorting algorithm, it is also called the partition-exchange sort.

MergeSort

Merge sort is another sorting algorithm. This algorithm divides the array into two halves, then recursively sorts them, and finally merges the two sorted halves.

Strassen’s Matrix Multiplication

It is an algorithm for the multiplication of matrices. It is named after Volker Strassen. It has proven to be much faster than the traditional algorithm while working with large matrices.

Closest Pair of Points

This algorithm of the closest pair of points emphasizes finding out the closest pair of points in a metric space where we are given n points, such that the distance between the points is minimal.

Cooley-Tukey Fast Fourier Transform (FFT) algorithm: The Cooley-Tukey Fast Fourier Transform algorithm is named after J. W. Cooley and John Turkey. It follows the approach of Divide and Conquer and has a complexity of O(nlogn).

Karatsuba algorithm for fast multiplication: It is one of the fastest multiplication algorithms of the traditional time which is invented by Anatoly Karatsuba in the late 1960 and got published in 1962. It multiplies two n-digit numbers in such a way that it reduces it to at most single-digit.

Algorithm for Divide and Conquer Strategy:

DAC(x, i, j)
{
    if(small(x, i, j))
         return(Solution(x, i, j))
    else 
         k = divide(x, i, j)                    // f1(n)
         p = DAC(x, i, mid)                 // T(n/2)
         q = DAC(x, mid+1, j)             // T(n/2)
         r = combine(p, q)                  // f2(n)
   return(r)
}

The recurrence relation for the Divide and Conquer strategy is given as :

    T(n) = O(1) if n is small
           f1(n) + 2T(n/2) + f2(n)

This is all about the divide and conquer strategy. Take a look over the next articles to know in brief about all the applications of the Divide and Conquer strategy.