Algorithms and decomposition

An algorithm is a method: a sequence of steps that, followed exactly, turns an input into the answer you wanted, and stops. The word sounds academic and the thing is ordinary — long division is an algorithm, and so is the way you look up a word in a dictionary.

What makes it worth naming is the discipline it forces. An algorithm has to be complete (no step says "and then figure it out"), unambiguous (no step can be read two ways), and finite (it ends). Prose fails all three constantly and nobody notices, because the reader repairs it. A machine does not repair anything.

#Writing one before you write code

Here is a task: find the largest number in a list.

Most people can do this instantly and cannot say how. Watch yourself do it on [3, 9, 4, 1, 8] and the method appears:

1. Remember the first number as "the largest so far".
2. Look at the next number.
3. If it is bigger than "the largest so far", make it the new "largest so far".
4. Repeat from 2 until there are no more numbers.
5. "The largest so far" is the answer.

That is an algorithm, and it is already good enough to translate into any language. Notice what it needed: a piece of state ("the largest so far"), a loop (step 4), and a decision (step 3). Almost everything you write is those three.

Here it is as code, and the mapping is one line per step:

static int largest(int[] xs) {
    int largestSoFar = xs[0];                 // 1. remember the first
    for (int i = 1; i < xs.length; i++) {     // 2, 4. look at the next, repeat
        if (xs[i] > largestSoFar) {           // 3. is it bigger?
            largestSoFar = xs[i];             //    then it is the new largest
        }
    }
    return largestSoFar;                      // 5. the answer
}

Now break it. What does it do on an empty list? Step 1 says "remember the first number" and there is no first number. The algorithm is wrong, and the only reason you did not notice is that the example had five numbers in it.

Run it and the machine is blunter about it than the prose was:

9
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
	at Largest.largest(Largest.java:3)
	at Largest.main(Largest.java:14)

The first call printed 9. The second threw on line 3 — xs[0], the step that says "remember the first number". The algorithm was not almost right; it had no answer for this input and said so by crashing.

Which is the better outcome, incidentally. Had step 1 said "start with zero", the empty list would have returned 0 — a plausible-looking number that is not the largest of anything, and that nobody would ever notice.

#The assumption underneath most beginner bugs

There is a single faulty belief that computing-education research finds under a great many early mistakes, named by Roy Pea in 1986 as the superbug: the assumption that there is a hidden mind in the machine — something that understands what you meant.

Nobody says this out loud. It shows up in what people write. Pea named three shapes of it, and they are recognisable in code written today:

• Intentionality. Expecting the machine to act on the purpose of your program rather than its statements. A variable named total is expected to total things; a method called validate is expected to reject bad input even where nothing was written to reject it.
• Parallelism. Expecting a line written earlier to keep watching. Writing if (balance < 0) reject(); near the top and expecting it to apply later, when something else changes balance — as though the condition were a standing rule rather than one instruction that ran once.
• Egocentrism. Expecting the machine to supply what you left unsaid, because it was obvious to you. The empty list, the missing field, the negative amount.

All three are the same mistake in different clothes: the program means exactly what it says and nothing you also had in mind. The name is the point — once you can call it by name, you start noticing yourself doing it.

That is also why the two questions below work. They both force the unsaid thing to be said.

#Decomposition: splitting before solving

The real skill is not solving a hard problem. It is noticing that a hard problem is three easy ones.

"Send a weekly report of each customer's spending." That is not a problem you can start typing. Split it:

Send a weekly report of each customer's spending
├── Decide which week
├── Get the orders in that week
├── Group them by customer
├── Add up each customer's total
├── Turn the totals into a readable report
└── Send it

Every leaf is now something you could describe as steps, and several are things somebody has already written for you. That is what decomposition buys: it turns "I don't know how to do this" into "I don't know how to do step 4", which is a much better problem to have.

Split until each piece is either obvious or someone else's. That is the whole rule, and it is the one people skip when they are in a hurry — and then spend an afternoon stuck on something that was four problems wearing a coat.

#The two questions that end most confusion

When you are stuck, they are almost always these:

1. What exactly am I given, and what exactly do I want? Write both down. Half of being stuck is having never made this precise. "A list of orders" — of what shape? "A total" — per customer, or overall? Including tax?
2. Can I do it by hand on a tiny example? If you cannot do it on three rows with a pen, you cannot write it. The method you use on paper is the algorithm; you just have not written it down yet.

#Try it yourself

#Misconceptions

• "Algorithms are advanced." The ones you use daily are not. Sorting a hand of cards and looking up a phone number are algorithms, and you already know them.
• "I'll work it out as I type." Sometimes, for something small. For anything you cannot hold in your head, typing first produces code shaped like your confusion.
• "Decomposition is over-engineering." Splitting a problem on paper costs nothing and creates no code. Over-engineering is building abstractions for splits you have not yet needed.