Computer Science › Section F · Algorithms › Topic F.1
The concept of an algorithm
Computer science is built on algorithms, so the word needs a precise meaning. This topic pins down the four properties every algorithm must have and separates an algorithm from the program that represents it and the process that carries it out.
Algorithms are everywhere
You follow algorithms all the time: a recipe, the directions to a friend's house, the long multiplication you learnt at school. A computer follows one at its lowest level too. As the topic "Program execution and the machine cycle" showed, the CPU repeats fetch, decode and execute until it meets a halt instruction. The opening topic, "Algorithms and what computer science studies", introduced an algorithm as a list of instructions for a task and noted the precision a computer needs. This topic turns that into a definition sharp enough to decide whether a given list of instructions really counts.
A precise definition
Computer scientists use this definition: an algorithm is an ordered collection of steps, each one unambiguous and executable, that together define a process which always comes to an end. Every word earns its place. Ordered means the sequence of the steps is fixed. Executable means each step can actually be carried out. Unambiguous means each step has exactly one meaning, so the person or machine following it never has to guess. Terminating means that following the steps leads, sooner or later, to a finish. A list of instructions that breaks any one of these four requirements is not an algorithm in the strict sense.
Ordered steps
In the simplest case the steps are carried out one after another in the order written, which is called sequencing. Ordered does not have to mean a single line of steps, though. A parallel algorithm has several sequences of steps that run at the same time on different processors, splitting apart and joining up again; the topic "Other architectures: pipelining and multiprocessors" describes the hardware for this. In a circuit such as the flip-flop from "Bits, gates, and flip-flops", each gate performs one step, and the order comes from cause and effect: a gate acts when the signals reaching it change. What matters is that the structure of the order is well defined.
Executable and unambiguous
A step is executable, or effective, if it can really be done. "Write down the largest prime number" fails, because there are infinitely many primes and so no largest one exists. "Divide the total by the number of items" fails whenever there are no items. A step is unambiguous if the current situation determines exactly what to do. "Season to taste" and "pick a big number" fail, because two people following them could do different things. Following an algorithm should need no creativity or judgement at all, only the ability to carry out instructions exactly.
A terminating process
The last requirement is that the process must end. This comes from theoretical computer science, which separates problems whose answers can be produced by a process that finishes from those that cannot; section M, "Theory of computation", returns to it. In practice the word is used more loosely. A thermostat or a heart monitor runs forever by design, and some argue it is really one terminating algorithm repeated again and again. School long division also stretches the word: dividing 1 by 7 gives 0.142857142857..., with the digits repeating forever, so the process never ends unless you are told how many digits to stop at.
Worked example: is this an algorithm?
A pile of cards each shows a whole number. Instructions: (a) Look at the top card and remember its number. (b) For each remaining card in turn, if its number is smaller than the one you remember, remember the new number instead. (c) Announce the number you remember. 1. Ordered: the steps run a, b, c, and step b visits the cards in pile order. 2. Executable: comparing two whole numbers is always possible. 3. Unambiguous: "smaller than" has one meaning, and ties change nothing. 4. Terminating: the pile is finite, so step b ends. All four hold, so it is an algorithm. On the pile 42, 17, 58, 9, 23 it announces 9. By contrast, "keep drawing cards until you reach the smallest" fails: you cannot know a card is the smallest until you have seen them all.
Worked example: a loop that never ends
Here is a fragment in the notation used throughout this section. The line starting while checks its condition before each pass and repeats its indented body for as long as the condition is true, and != means "is not equal to".
1. Trace the values: 10, 7, 4, 1, -2, -5, and so on. 2. Each pass subtracts 3, and 10 is not a multiple of 3, so Start jumps from 1 straight to -2 and never equals 0. 3. The condition stays true forever, so this is not an algorithm. 4. Fix: test while (Start > 0). Now the loop runs 4 times and stops with Start = -2.
Algorithms are abstract
An algorithm is an idea, separate from any way of writing it down, much as a song is separate from its sheet music or a recording. The area of a trapezium (a trapezoid in US usage) can be written as the formula \(A = \frac{h(a + b)}{2}\), as the sentence "add the two parallel sides, multiply by the height and halve the result", or as a circuit. For parallel sides 3 and 5 and height 4, every version gives 16. The steps are the same, so the algorithm is the same; only the representation differs. A representation can also be too vague for a particular reader even when the algorithm behind it is perfectly precise, which is the subject of the next topic.
Programs and processes
Three related words are easy to confuse. An algorithm is the abstract method. A program is a representation of an algorithm, written formally so that a computer can carry it out. A process is the activity of carrying it out, the term used in "Coordinating the machine: processes and scheduling". One program can give rise to many processes: two people running the same spreadsheet program are running two processes. Software designed never to stop, such as an operating system, is still called a program, using the looser sense of algorithm.
Common mistakes to avoid
First, calling any list of instructions an algorithm: check all four properties, especially termination. Second, assuming that a loop which counts towards a target must reach it; test whether the steps can actually land on the value, as with Start jumping past 0. Third, mistaking an unclear representation for an unclear algorithm: "convert to Fahrenheit" is precise to a scientist and vague to a child, but the method is the same. Fourth, mixing up program and process: the program is the text, the process is the run.
Key takeaways
An algorithm is an ordered collection of steps, each unambiguous and executable, whose process always ends. Ordered steps may be sequential, parallel or ordered by cause and effect. Executable means each step can be done; unambiguous means each step has exactly one meaning. Termination rules out loops whose condition can never become false. Long division of 1 by 7 and a thermostat stretch the strict definition. An algorithm is abstract: a formula, a sentence and a circuit can all represent the same one. A program represents an algorithm; a process is the activity of executing it.
Flashcards
Flashcard
Ordered steps, each unambiguous and executable, whose process always ends
Test your understanding
Question 1 of 5
A recipe step says "Add salt and season to taste." Which property of an algorithm does this step fail?
Question 2 of 5
What happens when this fragment runs? X = 1, then while (X != 8): X = X + 2
Question 3 of 5
Which statement correctly describes a program?
Question 4 of 5
A textbook gives the trapezium area as A = h(a + b)/2; a worksheet says "add the parallel sides, multiply by the height and halve the result". What is the relationship?
Question 5 of 5
Dividing 1 by 7 by school long division produces 0.142857142857... with no end. In the strict sense, is this an algorithm?
