What an algorithm is, exactly

A problem is a contract between input and output. An algorithm is one way of honouring it, and correctness means honouring it on every input, not on the ones you tried.

A shop hands you the temperature readings from its cold store, one number per hour, and asks for the highest reading of the day. Before any code exists, notice something: two people would agree completely on what a right answer looks like, and could still write two completely different procedures to produce it.

That gap is the whole subject. The task can be written down once, precisely, and then judged. The procedures are many, and they differ in how much work they do. Keeping those two things apart is the first skill this course teaches.

Here is the task written down precisely. The input is a list of whole numbers with at least one entry. The output is a single number that appears somewhere in that list and is not smaller than any number in it. Nothing in that description says how to find it.

Now two procedures that both honour it. The first walks the list once, remembering the best reading seen so far. Run it, then read the second one below and predict its output before you run that.

The second procedure never keeps a running best. It asks, of each reading in turn, whether any reading in the list beats it, and reports one that nothing beats.

Same answer, both times, and there is no input on which they disagree. What differs is the work: procedure A looks at each reading once, procedure B compares every reading against every reading, which on six readings is thirty-six comparisons instead of six.

The words for this

A problem is the relationship between input and output, written so that a right answer can be recognised without knowing how it was produced. The description three paragraphs up is a problem. One particular list of readings is an instance of that problem.

The statement of a problem has two halves, and they are worth naming separately. The precondition is what is promised about the input: here, a list of whole numbers with at least one entry. The postcondition is what must be true of the output: here, that it appears in the list and nothing in the list exceeds it. Together they are the input/output contract.

An algorithm is a finite, unambiguous procedure that takes an input meeting the precondition and produces an output. Procedure A and procedure B are two algorithms for one problem. An algorithm is correct when, for every input meeting the precondition, it stops after finitely many steps and its output meets the postcondition.

That asymmetry is not a technicality. Here is a procedure that agrees with A and B on the readings above, and on most lists you would think to type, and is still wrong.

Starting best at zero silently added a precondition nobody agreed to: that some reading is positive. On a cold store, where every reading is below freezing, it returns 0, a number that never appeared. The postcondition said the output must appear in the list, so this procedure is not correct, whatever the test suite says.

Design and analysis are separate jobs

Design is producing an algorithm that meets the contract. Analysis is working out what that algorithm costs in time and memory, as the input grows, and proving that it is in fact correct. The two are separate jobs and they fail in separate ways.

A designed algorithm with no analysis is a guess: you do not know whether it is right, and you do not know whether it will still finish when the list has a million readings instead of six. An analysis with no algorithm is a wish. Most of this course alternates between the two on purpose.