What makes a method an algorithm?

Step 1 Warm-up recall

From M1.L1: write the three parts of a specification.

Your answer

Private: nothing you type here is sent or stored.

Step 2 Learning goal

By the end of this lesson you can:

• state the properties that make a method an algorithm (Foundation);
• write an algorithm for finding the largest item in a list (Core);
• explain why each step must be unambiguous (Core).

Step 3 A familiar example

A recipe that says “cook until done” relies on a cook’s judgement. A machine has no judgement, so each step must be exact enough that two different machines would do the same thing.

Step 4 Clear explanation

An algorithm is a finite, ordered set of unambiguous steps that produces the required output for every valid input. Four properties matter: it has defined input and output; each step is unambiguous; it is finite, so it stops; and it is correct, so the output meets the specification every time. The word comes from the name of a medieval scholar, and the idea was made exact in the twentieth century by logicians including Alan Turing.

The figure shows one algorithm for finding the largest number. It works because it keeps one piece of memory, the largest so far, and updates it only when it meets something bigger. The same specification has many algorithms; they can differ in clarity and in the number of steps.

Note what each step avoids. “Look at the next item” is exact because the order of items is fixed. “Pick a big one” is not an algorithm step because two machines could pick differently.

Step 5 Worked example (4 marks)

Is “keep adding numbers until the total feels large” an algorithm?

1. Test unambiguity: “feels large” has no exact meaning. (1 mark)
2. Test finiteness: nothing says when to stop. (1 mark)
3. So it fails two properties. (1 mark)
4. Repair: “add the numbers in the list one by one and stop at the end of the list; output the total”. (1 mark)

Step 6 Learner practice (instant-marked)

Step 7 Recap

• An algorithm is finite, ordered and unambiguous, and gives the right output for every valid input.
• The largest-so-far method needs one stored value.
• One specification can have many algorithms.

Step 8 Exit ticket (ungraded)

Rewrite “find a cheap hotel” as an algorithm with exact steps for a list of hotel prices.

Your answer

Private: nothing you type here is sent or stored.

Step 9 Go further (Extension)

Read the encyclopedia entry on algorithm and note one example you had not considered.