Try this trivial(!) paper folding activity to see the power of divide and conquer.

Learn about:

• divide and conquer
• decomposition

On Christmas Day or when wrapping presents (or a birthday) try this paper folding challenge. If there is a small child in the family, they are probably sat on the floor, surrounded by vast piles of half torn paper. Challenge everyone to do the following:

Find the biggest, thinnest piece of wrapping paper you can. Smooth it flat. Ask everyone to guess how many times they can fold it in half. Now, just fold it in half, then in half again, then in half again, halving the area of the paper each time. What is the challenge? Simply to fold it in half repeatedly like this just 10 or more times in total!

If they can’t suggest they try a slightly bigger piece of paper!

What has this to do with computing? Well it shows what is behind a powerful way to create fast algorithms: divide and conquer. The idea of divide and conquer is that to solve a problem, find a way to turn the problem in to an identical problem that is half as big. Then solve that problem in exactly the same way (i.e. recursively keep halving the size of the problem). The size of the problem decreases very, very rapidly until very soon it is so small it is trivial to solve (without any further dividing). Problem solved (quickly).

We are doing something similar with the paper. We repeatedly half the size of the paper, but are faced with the same problem, and very rapidly the size of the paper gets smaller and smaller (and its thickness gets similarly thicker and thicker).

This isn’t showing a problem getting simpler, as we want with algorithms to solve problems. With each fold we have made the problem twice as hard. It only takes 10 folds to become impossibly hard. This shows how quickly we change the complexity of the problem with this kind of halving approach.

With divide and conquer algorithms we turn this round. Instead of making a problem harder we find a way to make it simpler, but the same. Then something that might take a thousand steps to do a normal way can be done in 10 halving steps, or something that takes a million steps takes only 20 halving steps.

Divide and conquer is powerful because it harnesses the power of halving to turn something big into something tiny very quickly.

Dividing paper in to areas

We can recast paper folding as an actual divide and conquer style problem to solve, by setting the problem as being to fold a piece of paper so that it is divided in to a 256 separate areas by the folds.  You could do this using concertina style folds, folding a tiny strip down the side, then a second.  Each fold adds one more area to the total number. You will need 255 folds. It will take all night! This is a linear algorithm, knocking off a bit of the algorithm with each step taken.

If instead you take a divide and conquer style approach, and make the folds, halving folds, you get to the solution in only 8 steps – 8 folds and you are done. The first fold gives you 2 areas, the second gives you 4, the third gives you 8 areas, then 16 and 32, 64, 128 and 256 areas on the 8th fold. Job done quickly.