3
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ You will have to enlighten us on “boomerang”. $\endgroup$ – ctrl-alt-delor Jul 21 at 22:45
  • 1
    $\begingroup$ Divide and Conquer was originally a military term. You can look for example at the British conquest of India. $\endgroup$ – njzk2 Jul 21 at 23:23
  • $\begingroup$ Related: stackoverflow.com/questions/14415881/… $\endgroup$ – David says Reinstate Monica Jul 22 at 1:01
  • 3
    $\begingroup$ My teacher used the way we look for a word in a dictionary. $\endgroup$ – Jimbot Jul 22 at 12:40
  • 1
    $\begingroup$ My mother taught me binary search for finding words in a dictionary in the 1950's. $\endgroup$ – Patricia Shanahan Jul 22 at 13:43
12
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ +1 for the Hungarian dance example :) $\endgroup$ – DavidPostill Jul 22 at 12:41
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hello, and welcome to Computer Science Educators SE! While your example is good, you may want to add some explanation of why your example appropriately addresses the question. Thanks! $\endgroup$ – heather Jul 31 at 18:14
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would you mind providing a bit more explanation for why you think merge sort is a good example to use for teaching divide and conquer? Not every divide and conquer algorithm will be useful for teaching the concept of divide and conquer, so why do you think merge sort is? $\endgroup$ – thesecretmaster Sep 10 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.