Algorithms and MP0

Consider the following problem that uses computers in the historical sense of the word—humans performing computation, hence computers. You have a room full of people. Each knows their own age, but can’t or won’t perform any addition. Your goal is to compute the sum of all of the ages of everyone in the room—and to do so as fast as possible.

Assume that it takes one second to ask a question 1 and get a response 2. Also make the optimistic assumption that it takes no time to add two numbers together. Then it would take you 32 seconds to compute the entire sum yourself.

But now let’s say that you have help. How long would it take:

Keep in mind that a good solution should keep all of your helpers busy, and also requires communication between your team that you need to account for.

It’s common for computer scientists to solve a smaller version of a problem and then generalize it to a larger version. (For example, I’ll build a small college-only social networking website and then expand it later.) Let’s try that here. Compute how long it would take a group of 8 people to sum 1,024 ages. Do you see a pattern emerging?

Now return to the case where you are summing the ages of 32 people using a team of four, including yourself. Just to be safe, after computing the sum once, you rerun the calculation again—but get a different result! There must be a bug somewhere 3!

The first step in locating a bug is to always think carefully about what could be causing the problem. Come up with at least five different sources of error that may be affecting the result of your calculation.

Next, develop a foolproof procedure for identifying the cause of the problem. You want to be just as methodical in approaching how you identify the problem as you were in developing your original solution. Debugging is always frustrating. Something is going wrong and you don’t know why! But if you approach the debugging problem like a computer scientist, you can usually come up with a good debugging algorithm. And then get back to the problem you were actually trying to solve.

Fresh of the experience of debugging your system, you decide to be more proactive in the future. Debugging is reactively waiting for problems to emerge and then trying to fix them. Testing is proactively testing things to make sure they work properly. When you test the things that you build as you go, it is much less likely that you will experience complex and difficult to find problems.

Return to the sources of error that you identified above. For each, develop a testing procedure that will ensure that you can identify the problem before it happens.

Note that while it may be tempting to try to test your system by ensuring that it can correctly compute sums for all possible inputs, this is unlikely to be feasible. Even if all 32 people are children and ten years old or younger, the space of possible inputs grows extremely quickly.