Divide and Conquer at Five Levels

  1. Child: Imagine you have a big puzzle to solve. It’s really hard to solve the whole puzzle at once, right? So, what do you do? You break it into smaller parts, solve each part, and then put those parts together to complete the whole puzzle. That’s exactly what ‘Divide and Conquer’ is - solving a big problem by breaking it into smaller problems.

  2. Teenager: When you have a big problem, it’s often easier to divide it into smaller parts, solve each of these smaller parts, and then combine those solutions to solve the original problem. This idea is known as ‘Divide and Conquer’. It’s like cleaning your room. Instead of thinking about the whole room, you might break it down - clean the desk, then the bed, then the floor. Each part is easier to handle.

  3. Undergrad: In computer science, ‘Divide and Conquer’ is an important algorithm design paradigm based on multi-branched recursion. It works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

  4. Grad Student: ‘Divide and Conquer’ is an effective method for the design of efficient algorithms. It involves three steps at each level of recursion: Divide the problem into a number of subproblems that are smaller instances of the same problem. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner. Combine the solutions to the subproblems into the solution for the original problem.

  5. Colleague: The ‘Divide and Conquer’ paradigm optimizes the time and space complexity of algorithms in many cases, especially for problems such as Sorting (Merge Sort, Quick Sort), Multiplication of Large Integers (Karatsuba Algorithm), Matrix Multiplication (Strassen’s Algorithm), Closest Pair of Points, and many others. However, the efficient implementation of this paradigm requires a deep understanding of recursion and problem-solving skills to identify if a problem can be broken down into similar sub-problems, solve the base cases, and combine the results properly.

Socrates Teaches Divide and Conquer

  1. Have you ever had to tackle a big project or task that seemed overwhelming at first?

  2. Yes, we all have! Now, instead of trying to do the entire project all at once, did you find it more manageable to break it down into smaller, individual tasks?

  3. That’s right! When we break down a big problem into smaller parts, we can focus on each part individually, making the overall problem easier to solve. Can you think of how we might use a similar approach when dealing with complex problems in computer science or mathematics?

  4. You’re on the right path! In computer science, we often encounter problems that seem overwhelming at first. However, we can break these problems down into smaller, more manageable parts. This approach can help make the problem easier to solve. Can you guess what this problem-solving strategy is called?

  5. Exactly! We call this strategy “Divide and Conquer”. It’s a powerful method used in computer science, where we divide the problem into smaller sub-problems. Then we solve those sub-problems, and combine their solutions to solve the original problem. It’s a clever way of dealing with complex problems, don’t you agree?

Divide and Conquer Strategy

One big problem may be hard to solve, but two problems that are half the size may be significantly easier. In these cases, divide-and-conquer algorithms fare well by doing just that: splitting the problem into smaller subproblems, solving the subproblems independently, and combining the solutions of subproblems into a solution of the original problem.

The situation is usually more complicated than this and after splitting one problem into subproblems, a divide-and-conquer algorithm usually splits these subproblems into even smaller sub-subproblems and so on, until it reaches a point at which it no longer needs to recurse.

A critical step in many divide-and-conquer algorithms is the recombining of solutions to subproblems into a solution for a larger problem.

Given a function to compute on n inputs, the divide and conquer strategy splits the input into k distinct subsets, yielding k subproblems. These subproblems must be solved and then a method must be found to combine subsolutions into a solution of the whole.

If the subproblems are large, then the divide and conquer strategy may possibly be reapplied. Often the subproblems resulting from a divide and conquer design are of the same type as the original problem. For those cases, the reapplication of the divide and conquer principle is naturally expressed by a recursive procedure.

Now smaller and smaller subproblems of the same kind as the original problem are generated, eventually producing subproblems that are small enough to be solved without splitting.

We can write a program template which mirrors the way an actual program based upon divide-and-conquer will look. By a program template we mean a procedure whose flow of control is clear, but whose primary operations are specified by other procedures whose precise meaning is left undefined.

Richard Feynman Explanation

Well, imagine that you’re at a party and you’ve been given the task of finding a particular friend named Joe, but the place is jam-packed. How would you go about it?

You could, of course, go through the crowd one by one, asking each person, “Are you Joe?” This would be incredibly time-consuming and inefficient. So, what can you do to find Joe more quickly?

Here’s where the ‘Divide and Conquer’ approach comes in, something we often use in computer science to solve complex problems. You could divide the crowd into two halves. You then ask someone in the first half if Joe is in their half. If they say ‘yes’, you focus your search only in that half and ignore the other. If they say ’no’, you move to the other half.

You keep dividing the crowd (or problem) into smaller and smaller sections (or sub-problems) until you find Joe (or solve the sub-problem). By doing this, you have significantly reduced the amount of time and effort to find Joe in that large crowd.

Similarly, ‘Divide and Conquer’ algorithms in computer science work by repeatedly breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. It’s like dealing with a large, complex puzzle by tackling smaller pieces of it one by one.

Recursive Program Template

Let the n inputs be stored by the array called input. Here is the program template for divide and conquer:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def solve(p, q)
   input 
  # 1 <= p <= q <= n 
  if small(p, q)
    return compute(p, q)
  else
    m = divide(p, q)
    # p <= m < q 
    solution = combine(solve(p, m), solve(m + 1, q))        
  end
end

small(p, q) returns true if the input size q - p + 1 is small enough so that the answer can be computed without splitting. If so, the function compute() is invoked. Otherwise the function divide (p, q) is called. This function returns an integer which specifies where the input is to be split.

Let m = divide(p, q). The input is split so that input(p, m) and input(m+1, q) define instances of two subproblems. The subsolutions x and y respectively of these two subproblems are obtained by recursive application of solve().

The combine(x, y) is a function which determines the solution to input[p, q] using the solutions x and y to the subproblems input[p, m] and input[m+1, q]. If the sizes of the two subproblems are approximately equal then the computing time of solve() is naturally described by the recurrence relation:

1
2

T(n) = compute(n), n small
       2T(n/2) + f(n), otherwise

T(n) - Time for solve() on n inputs. compute(n) - Time to compute the answer directly for small inputs f(n) - Time for divide and combine

TIP

Recurrence relations will often arise for divide and conquer based algorithms.

For divide and conquer based algorithms which produce subproblems of the same type as the original problem it is natural to first describe such an algorithm using recursion. But to gain efficiency it may be desirable to translate the resulting program into iterative form.

Iterative Program Template

The iterative form of divide and conquer program template:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def solve(p, q)
  # declare a stack of appropriate size
  # set the stack to empty 
  top = Stack.new
  
  while(!small(p, q))
    m = divide(p, q)
  end
  while top != 0
    # decrement top
    # process the second recursive call
    # combine two solutions into one
  end
end

Strategy

Problems with optimal substructure can be divided into similar but smaller subproblems. They can be divided over and over until subproblems become easy. Then subproblem solutions are combined for obtaining the original problem’s solution.

The divide-and-conquer strategy solves a problem by:

  1. Breaking it into subproblems that are themselves smaller instances of the same type of problem
  2. Recursively solving these subproblems
  3. Combining the solutions to the subproblems

The real work is done piecemeal, in three different places:

  1. In the partitioning of problems into subproblems
  2. At the very tail end of the recursion, when the subproblems are so small that they are solved outright
  3. In the gluing together of partial answers.

These are held together and coordinated by the algorithm’s core recursive structure.

The divide-and-conquer strategy is a common approach in computer science and mathematics for solving complex problems. It is based on the principle of breaking down a large problem into smaller, more manageable subproblems, solving each of these subproblems, and then combining their solutions to solve the original problem.

The process of dividing the original problem is often performed recursively, breaking down each subproblem into even smaller sub-subproblems until a base case is reached. The base case refers to the simplest possible instance of the problem that can be solved directly without further subdivision.

A central element in many divide-and-conquer algorithms is the combination or merging of solutions to the subproblems. Once the base case is solved, the solutions to the smaller subproblems are combined step-by-step, leading up to the solution to the original problem.

Algorithm Implementation

In practice, a divide-and-conquer algorithm is usually implemented as a recursive function or procedure. The function takes as input the problem to be solved and outputs the solution. The input is split into several subsets, each representing a subproblem. The function is then called recursively on each subset. The base case checks if the problem is small enough to be solved directly, otherwise, the problem is further divided.

Let’s illustrate this with the provided pseudocode in Ruby:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def solve(p, q)
   # 1 <= p <= q <= n 
  if small(p, q)
    return compute(p, q)
  else
    m = divide(p, q)
    # p <= m < q 
    solution = combine(solve(p, m), solve(m + 1, q))        
  end
end

In this code:

  1. small(p, q): This function checks if the current problem, defined by the range [p, q], is small enough to solve directly.

  2. compute(p, q): This function is used to solve the problem directly when it is small enough.

  3. divide(p, q): This function is used to divide the problem into two subproblems. It returns the point ’m’ at which to split the input.

  4. combine(solve(p, m), solve(m + 1, q)): This line represents the recursive calls to solve the subproblems, and then combines their results into a solution for the current problem.

Time Complexity

A common way to analyze the time complexity of a divide-and-conquer algorithm is to use a recurrence relation. The time T(n) it takes to solve a problem of size n is expressed in terms of the time it takes to solve smaller instances of the problem.

1
2

T(n) = compute(n), n small
       2T(n/2) + f(n), otherwise

Here, compute(n) is the time to compute the answer directly for small inputs, 2T(n/2) is the total time for solving the two subproblems, and f(n) is the time for dividing the problem and combining the results.

Iterative Solution

While recursive solutions are often more straightforward to implement and understand for divide-and-conquer problems, they can lead to problems such as stack overflow for large inputs. Therefore, in some cases, it may be beneficial to implement an iterative version of the algorithm.

An iterative implementation of a divide-and-conquer algorithm often makes use of a data structure such as a stack or a queue to keep track of the subproblems that still need to be solved.

Similar Concepts

There are several algorithms and concepts in computer science that are similar to Divide and Conquer, either by involving a recursive approach or by breaking down problems into smaller parts. Here are some of them:

  1. Recursive Algorithms: Recursive algorithms often break down a problem into smaller subproblems in a manner similar to divide and conquer. However, not all recursive algorithms divide the problem into equal parts or combine the results of the subproblems to get the final answer.

  2. Dynamic Programming: Dynamic programming is a methodology that solves complex problems by breaking them down into simpler subproblems, and stores the results of these subproblems to avoid computing the same results again. This is similar to divide and conquer, but differs in that subproblems are often overlapping in dynamic programming, while they are disjoint in divide and conquer.

  3. Backtracking: Backtracking also breaks down the problem into smaller subproblems, but differs from divide and conquer in that it involves exploration and discarding some solutions if they are found to be unworkable.

  4. Branch and Bound: This technique is used in optimization problems. It divides the problem into subproblems (branch) and uses bounds to eliminate unprofitable subproblems.

  5. Merge Sort and Quick Sort: These are specific examples of algorithms that follow a divide and conquer strategy, by breaking down the problem (sorting a list) into smaller parts, sorting them independently, and then combining them.

  6. Binary Search: Another example where a problem (searching in a sorted list) is divided into smaller parts, one of which is discarded and the search continues in the remaining part.

  7. Master Theorem: It is a method that solves recurrence relations which often arise when analyzing the time complexity of divide and conquer algorithms.

All these techniques share the broad idea of solving a large problem by breaking it down into smaller, more manageable subproblems. The specifics of how this is done and how the solutions to the subproblems are used to solve the original problem differ between the techniques.

Q&A

  • Does Divide and Conquer using Division?

The term “Divide and Conquer” in computer science doesn’t strictly relate to the mathematical operation of division, as in dividing numbers. Instead, it refers to a strategic approach to problem-solving.

In a “Divide and Conquer” algorithm, the problem is divided (broken down) into smaller subproblems. These subproblems are independently solved, and then their solutions are combined to solve the original problem.

This division is usually done in a recursive manner, where each subproblem is further divided until we reach a stage where the subproblem can be solved directly without any further division. This base condition typically involves a very simple problem, the solution of which is easy to compute. Once the base condition is reached, recursion stops and the solutions of the subproblems are combined up the recursive call stack to solve the bigger problem.

So while it’s not “division” in the arithmetic sense, it is a process of breaking down a complex problem into simpler parts.

  • In binary search we are dividing the given array by half. So it seems like Divide and Conquer uses division. What are the examples where Divide and Conquer does not use division?

Indeed, the term “divide and conquer” can sometimes be a little misleading. It doesn’t necessarily mean literal division, but rather breaking a problem down into smaller, more manageable subproblems. Sometimes this involves division (like binary search or merge sort), but not always.

A classic example where “division” is not literally used is the QuickSort algorithm. QuickSort is a divide and conquer algorithm that sorts an array or list of items.

In QuickSort, the “division” part is done by selecting a “pivot” element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The pivot is then in its final position, and the same process is recursively applied to the sub-arrays.

Here, the array is not divided into equal halves, the sizes of the partitions depend on the pivot and the elements in the array. Yet, this is still a divide and conquer strategy, because the problem (sorting the whole array) is divided into smaller problems (sorting the two partitions).

Here’s an example of quicksort in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

print(quicksort([3,6,8,10,1,2,1])) # prints [1, 1, 2, 3, 6, 8, 10]

So, while “divide and conquer” often involves splitting a problem into roughly equal halves, it doesn’t always. The key concept is not the act of division, but the act of breaking a larger problem down into smaller subproblems that are easier to solve.

  • Why QuickSort is not using Decrease and Conquer?

QuickSort is considered a divide and conquer algorithm because it partitions (divides) the input into two subarrays and then recursively sorts each subarray independently. The dividing step in QuickSort doesn’t just make the problem slightly smaller (as in decrease and conquer), it creates two new, independent subproblems.

In contrast, a decrease and conquer algorithm typically solves one smaller instance of the problem and uses that to solve the larger instance. In other words, decrease and conquer problems solve a single subproblem, while divide and conquer strategies tackle multiple subproblems.

So, although the partition in QuickSort doesn’t necessarily split the array into two equal halves, it still generates two independent subproblems to be solved, fitting the paradigm of divide and conquer.

Both binary search and QuickSort are examples of Divide and Conquer strategy, not Decrease and Conquer.

In binary search, the problem size is halved (or divided) at each step until the desired element is found, making it a clear example of the Divide and Conquer approach.

Similarly, QuickSort divides the input array into two smaller arrays around a pivot element. This division is performed recursively until the base case (an array of one or zero elements) is reached. Hence, it’s also a Divide and Conquer algorithm.

In contrast, a Decrease and Conquer strategy involves decreasing the problem size by a constant at each step, rather than dividing it into subproblems. An example of a Decrease and Conquer algorithm is the Insertion Sort algorithm, where in each iteration, one element is removed from the input data, processed, and then added to the already sorted section of data.

  • So the division mathematical operator is not used in Divide and Conquer but the concept of divide is used?

That’s correct. The term “divide” in “divide and conquer” is more conceptual than mathematical. It refers to breaking down a problem into smaller, more manageable subproblems. These subproblems are usually (but not always) similar or identical to the original problem. The subproblems are then solved, and their solutions are combined to create a solution to the original problem.

This division of the problem doesn’t necessarily involve the mathematical operation of division (as in dividing one number by another). For example, in the QuickSort algorithm, the array is “divided” into subarrays based on the pivot element, but this process doesn’t involve any mathematical division.

So yes, the concept of division in divide and conquer is about partitioning or breaking down the problem, rather than the mathematical operation of division.

Summary

Divide-and-conquer is a fundamental algorithmic technique for solving problems. It is applicable to a broad range of problems and is often used in combination with other techniques, like recursion or iteration. This strategy provides an efficient and effective way to design algorithms.