AQA GCSE Computer Science

What an algorithm is

An algorithm is an ordered list of steps for getting a task done, each one precise enough to follow exactly as written. A recipe, a set of directions to a shop and the method for long multiplication are all algorithms, and none of them needs a computer. What makes something an algorithm is that each step is precise enough to be followed without any further judgement, that the steps come in a definite order, and that the sequence finishes.

A computer program is an implementation of an algorithm: the same algorithm can be written as a Python program, a C# program or a VB.NET program, and each of those is a different program for one algorithm. It follows that an algorithm is not a program. The algorithm is the idea, and the program is that idea written in a language a computer can run.

Inputs, processing and outputs

Nearly every algorithm can be described in three parts. The inputs are the data the algorithm is given, the processing is what it does with that data, and the outputs are the results it produces. In this algorithm for the mean of two numbers, the two lines that take data in are the inputs, the middle line is the processing and the last line is the output.

a ← USERINPUT
b ← USERINPUT
mean ← (a + b) / 2
OUTPUT mean

Being able to point at these three parts in an unfamiliar algorithm is the first step in working out what it does. Values that are read in, and anything taken from a file or a sensor, are inputs. Assignments and calculations are processing. Anything displayed, printed or sent elsewhere is output.

Decomposition

Decomposition means splitting a problem into smaller parts, each of which does one identifiable job, and any of those parts may be split again in the same way. A quiz game, for example, splits into choosing a question, showing it, reading the answer, checking the answer and updating the score, and "checking the answer" could split again into comparing text and ignoring capital letters.

Decomposition works because small problems are easier to understand, write and test than one large one. Different people can write different parts at the same time, a part that works can be reused elsewhere, and when something goes wrong the fault is easier to find because it lies in one identifiable part. In a program each sub-problem usually becomes a subroutine.

Abstraction

Abstraction is leaving out the detail that a problem does not need, so that attention stays on what does matter. What counts as unnecessary depends on the purpose. A map of a railway network leaves out the real distances, the curves in the track and the buildings, and shows only the stations and how they connect, because that is all a passenger needs to plan a trip.

In programming, abstraction means a programmer works with the parts of a problem that matter and ignores the rest. A program that models a bouncing ball may need only its position, its speed and its mass, and not its colour or the stitching on it. Using a subroutine is also abstraction: the programmer needs to know what it does and what to give it, and not how it does it.

Using a systematic approach

Solving a problem systematically means working through it in a set order instead of writing code and hoping. A common order is to state the problem clearly, decompose it, identify the inputs and outputs of each part, and decide what abstraction is appropriate. The next step is to write each part as an algorithm, in pseudo-code or as a flowchart, and finally to trace it by hand with some sample data to see whether it behaves as intended. Only then does it become program code, which is then tested and refined in the light of the results.

Comparing algorithms

More than one algorithm can solve the same problem. Sorting a list of names, finding a value in a list and finding the shortest route between two places can each be done in several ways, and the algorithms differ in how much work they do. The efficiency of an algorithm here means its time efficiency: an algorithm is more efficient than another if it takes fewer steps to solve the same problem, particularly as the amount of data grows.

Efficiency is compared by looking at how the number of steps changes when the input becomes larger. An algorithm that looks at every item in a list of a million items may perform a million comparisons, whereas one that discards half of the remaining items with each step needs only about twenty. The searching and sorting algorithms in the notes that follow are the main examples of this difference.