Divide & Conquer

An effective strategy for coding & colonialism.

A divide and conquer algorithm is a strategy of solving huge problems by

1. Breaking the problem into smaller sub-problems
2. Solving the sub-problems
3. Combining them to get the desired output.

For efficiently applying the algorithm, we use a recursive approach:

1. Divide: Divide the problem into several sub-problems using recursion.

2. Conquer: Solve the smaller sub-problems recursively. If the sub-problem is small enough to be individually solved, then solve it directly.

3. Combine: Combine the solutions of the sub-problems that are part of the recursive process to solve the actual problem.

When should we use this Algorithm?

This algorithm will be useful if we have a problem that closely relates to the divide and conquer algorithm. We can use this algorithm where the problem can be divided into sub-problems but we have to make sure that we do not have to solve the same sub problem several times. If the same sub-problem has to be solved several times then this problem is likely to be solved by a dynamic approach rather than Divide and Conquer Algorithm.

How to implement Divide & Conquer?

Several critical steps need to be followed during implementing the divide and conquer approach:

1. There could be several sub-problems to a problem.The correct sub-problems need to be chosen involved in the solution. In most scenarios, we divide the problems into two equal sections.
2. We solve each sub-problems recursively. So we need to carefully decide the input parameters for the recursive call of each sub-problem.
3. The correct base case is essential for the correctness of the divide and conquer solution. We need to identify the smallest or trivial version of the sub-problem for which we already know the solution.
4. For implementing the conquer stage, we need to identify the correct operation to combine the solutions of sub-problems to get the final answer.

Let us look at some examples to help us understand this implementation:

1. Divide and conquer solution of finding max and min:

Step 1: Divide the array into two equal parts around mid-value.

Step 2: Conquer: Recursively find the min and max of both left and right parts.

Step 3: Combine: Compare the max and min of both halves to get the max and min of the whole array.

Step 4:

Base case 1: If the sub array size is 1, return the element as both max and min.

Base case 2: If sub array size is 2, compare both elements and return max and min among them.

2. Divide and conquer solution of finding max sub array sum:

We divide the array into two equal sub arrays: X[I … mid] and X [mid + 1 … r]. Then the sub-array X[i … j] with maximum sum must lie in one of these places:

1) Entirely in the left sub-array X[I…mid]

2) Entirely in the right sub-array X[mid+1…r]

3) Sub array crossing the midpoint. This includes some rightmost elements of the left sub array and some leftmost elements of the right sub array.

Divide: Calculate the middle index i.e., mid = I + (r — I)/2.

Conquer: Recursively find the maximum sub array sum of left and right halves.

Combine: Calculate the maximum sub array that crosses the midpoint and takes the maximum of all three possibilities. Base case: When I = = r, there is only one element in the array, and we can directly return the max sub array sum as X[I] or X[r].

Let us look at the algorithm with the help of diagrams:

Source

Divide and Conquer is used in Quick Sort Algorithm. We will learn more about it in upcoming bulletins. Source

The Algorithm:

DAC(a, i, j)  //Method which follows the DAC approach.
{ 
if(small(a, i, j))           //Base case(smallest problem)
  return(Solution(a, i, j)) 
else 
  m = divide(a, i, j) // f1(n) 
  b = DAC(a, i, mid) // T(n/2) 
  c = DAC(a, mid+1, j) // T(n/2) 
  d = combine(b, c) // f2(n) 
  return(d) 
}

Why should we use this algorithm?

● The complexity for the multiplication of two matrices using the naive method is O(n³), whereas using the divide and conquer approach the complexity reduces to O(n ^ 2.81). The change makes a big difference when the value of n is large. The use of this approach also simplifies other problems, such as the Tower of Hanoi.

● This approach is suitable for multiprocessing systems.

● It makes efficient use of memory caches.

Upcoming topics for the blogs:

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.