A real world example for the divide and conquer method

Question

Can someone give a real world example for the divide and conquer method? For example, I've heard the boomerang used to explain the idea of a loop back address. What is a real world example we can use to teach students about the divide and conquer method before going to more complex algorithms?

Answer 1

Back around 1985, Susan Merritt created an Inverted Taxonomy of Sorting Algorithms. The idea is that to sort an array you have two phases, the split phase and the join phase. She divided the various algorithms into two types easy split/hard join and hard split/easy join varieties. Merge sort is of the former type. Quick sort is the latter.

But all sorts, envisioned in this way are divide and conquer. Her original paper (part of her doctoral work) is a wonder and worth exploring by any CS teacher.

Answer 2

The simplest example that still bears enough complexity to show what's going on is probably merge sort. It's no coincidence that this algorithm is the classical example to begin explaining the divide and conquer technique.

I am not sure at what level you teach, but your students should be comfortable with both recursion and inductive proofs before venturing far into this territory.

Coincidentally, there is a list of divide and conquer algorithms found here. It's a pretty long list, and might have cast too wide a net. I'm not convinced that I agree that all of the algorithms are genuinely divide and conquer. However, it could be that upon closer inspection, they are.

In any case, it's a great starting point to find algorithms to present to your students. Just be sure that you can clearly explain the central divide/conquer/combine throughline for any algorithms you choose to bring to your students. This area of algorithms is full of traps for unwary beginners, so your students will benefit greatly from thought and care put into your presentation.

Answer 3

These sorts of patterns are a bit tricky in real life. In nice easy computer-science land, every step is the same, just smaller. Merge sort is clearly the ultimate easy example of this.

In real life, we tend to break things up along useful lines. If we're sorting change, we first divide the coins up by denominations, then total up each denomination before adding them together. When we put together a puzzle, we divide out the edge pieces first, put them together, then build the rest of the puzzle on that. In war, we divide an opponent into pieces which cannot work as a cohesive unit, then crush them.

We see this in real life more often than blind divisions because we, as humans, know we can divide along useful lines. The closest I know of that is quicksort's attempt to find a middle index to partition with.

One thing I find tricky about these divide and conquer algorithms is that they look like an infinite regression. You keep proving you can sort lists as long as you can sort smaller lists.... which you know you can do because you can sort smaller lists... so on and so forth. Infinite regression is a serious faux pas in modern logic, so I think people may get confused by that. Showing that "if I can sort a list of length n, I can sort a list of length 2n" would be the more traditional mathematical induction approach.

Then again, all may be for naught, for it is quite clear the best use for divide an conquer in real life is to put together a thrilling Hungarian dance.

Answer 4

If you want to divide a long loaf of bread in 8 or 16 equal pieces, generally people cut it into two equal halves first and then cut each half into two equal halves again, repeating the process until you get as many pieces as you want - 8, 16, 32, or whatever. Almost nobody tries to divide the loaf into 8 pieces all at once - people can guess halves much better than eighths.

Answer 5

MergeSort is fairly easy to implement in Python and it's a straightforward divide-and-conquer algorithm. You keep splitting the collection in half until it is in trivial-to-sort pieces. This splitting reduces sorting from O(n^2) to O(nlog(n)).

Second example: computing integer powers. if the power is even, square base and integer divide exponent by 2. If it's odd, do the same and multiply by a factor of the base. This algorithm is O(log(n)) instead of O(n), which would come from computing an integer power with a simple loop.

Answer 6

The typical examples for introducing divide and conquer are binary search and merge sort because they are relatively simple examples of how divide and conquer is superior (in terms of runtime complexity) to naive iterative implementations. FFT can also be used in that respect.

Among these, merge sort is the best example. Binary search is a degenerate case for explaining divide and conquer because you divide the problem into two subproblems, but you discard one of them almost trivially, so you are not actually combining the solution of several subproblems but just solving one of them.

But on my experience (I have lectured that several years), merge sort makes it also very hard for many novice students to grasp the idea of divide and conquer because it combines too many different conceptual problems at the same time. In order to implement merge sort efficiently, they will need to understand the technique of divide and conquer, the execution tree that occurs under the hood, the implementation of the division phase (thus working with indices if you want efficiency) and the implementation of the conquer phase (linearly).

You can start with an easier example such as computing the average of an array:

def average(arr):
    assert arr, 'Expected non-empty array'
    if len(arr)==1:
        avg = arr[0]
        n = 1
    else:
        mid = len(arr)//2 # or any value with 0 < mid < len(arr)
        avgL, nL = average(arr[:mid])
        avgR, nR = average(arr[mid:])
        n = nL + nR
        avg = (avgL*nL + avgR*nR) / n
    return (avg, n)

This example introduces the idea (instead of the advantages) of divide and conquer in a way that all students can intuitively understand. The key point is to highlight that the recursive calls solve exactly the same problem but for small instances, and that you can use those solutions of smaller instances to solve the problem for the large instance.

The example may appear trivial for many professors, but it is already shocking for many students and it will let them focus on understanding the technique itself and its execution, rather than details and optimizations. The example can also serve as guinea pig for analyzing the complexity of several different scenarios, such as when the array is copied on each call instead of being passed as a slice reference, or when mid is chosen as one third or as a constant.

Moreover, this example will naturally raise questions among students about its complexity and the possibility of parallelizing the computation, which may make some of them enthusiastic and creative.

Afterwards you must of course explain and analyze merge sort and binary search, emphasizing on how important they are because they beat naive iterative implementations.