Algorithm design and problem-solving

What an algorithm is, and why the wording has to be precise

An algorithm is a sequence of steps that solves a problem. It does not have to be written in a programming language: a recipe, a set of directions and the instructions on a ticket machine are all algorithms. What makes something an algorithm is that the steps are in the right order, each step means only one thing, and the sequence finishes after a finite number of steps.

Every algorithm can be split into inputs, processes, outputs and storage. The inputs are the data the algorithm is given, the processes are the calculations and decisions it carries out, the outputs are the results it produces, and the storage is anything it has to hold on to while it is working. A school register algorithm takes each pupil's name as input, counts the present pupils as a process, prints a summary as output, and keeps a running total of the pupils marked present while it goes.

You may be asked to explain the purpose of a given algorithm, and that means two things. Stating the purpose is one sentence about what the whole algorithm achieves, such as 'it finds the largest number in a list'. Describing the processes means going through what the algorithm actually does, step by step: 'it sets the maximum to the first value, then compares every other value with the maximum and replaces it whenever it finds a larger one'.

Precision is required. Cambridge marks algorithms written in precise pseudocode, and x > y is acceptable where 'x is greater than y' is not. The same rule applies to the decision boxes of a flowchart: write the condition as an expression, not as a sentence. Use the conventions of the syllabus, with upper-case keywords such as DECLARE, INPUT and OUTPUT, and the assignment arrow ←.

• State the purpose in one sentence, then describe the processes in the order the algorithm carries them out.
• Name every variable the algorithm uses, every value it outputs and every point at which the user is prompted for input.
• Write conditions as expressions: x > y is acceptable, x is greater than y is not.

Decomposition and abstraction: breaking a problem into sub-systems

Every computer system is made up of sub-systems, and each sub-system is made up of further sub-systems. A school's computer system has sub-systems for teaching, attendance and reporting. The attendance sub-system has its own sub-systems for registration, absence checking and letters home. Each level does one job properly and passes its result up to the level above, so a problem that looks impossible at the top becomes a set of small jobs at the bottom.

Decomposition is breaking a problem down into its component parts until each part is small enough to solve on its own. An online shop decomposes into a basket, a payment system and a delivery calculator, and the payment system decomposes further into card checking, address checking and order confirmation. Each part can then be designed, written and tested separately, and different programmers can work on different parts at the same time.

Abstraction is the other half of the job. It means removing the detail that does not matter for the problem in front of you and keeping only what does. A tube map is an abstraction of a railway network: it keeps the stations and the lines and throws away the real distances and the shape of the streets above them. In the same way, a program that works out a class average does not need to know a pupil's address or their shoe size.

Structure diagrams are the usual way to record decomposition on paper. The whole problem sits at the top, the main sub-problems sit underneath it, and each of those is broken down again. The diagram shows the whole solution at a glance, and each box can later become a procedure or a function in the finished program.

The program development life cycle: analysis, design, coding and testing

The program development life cycle has four stages, and Cambridge limits the examinable list to these: analysis, design, coding and testing. The stages run in order, but the cycle can be repeated: if testing uncovers a problem with the design, you go back and change the design.

In analysis you work out what the problem really is. That means abstracting the important details, decomposing the problem, and identifying the problem and its requirements: what the program must take in, what it must produce, and what it must do in between. Getting this stage wrong is expensive, because everything that follows depends on it.

In design you work out how the solution will be built, without writing the finished code. Decomposition carries on here, and the design is recorded as structure diagrams, flowcharts or pseudocode.

In coding you turn the design into program code and test it as you go. This is iterative testing: you check each procedure or function as soon as you write it, rather than waiting until the whole program is finished and trying to test everything at once.

In testing you run the finished program with planned test data and compare what it produces with what you expected. Testing is not proof that a program works; it is a search for errors, and the test data has to be chosen to try to make the program fail.

Sequence, selection and iteration, in pseudocode and in flowcharts

Sequence means the statements are carried out one after another, in the order they are written. It is the default, and the order matters: setting a total to 0 before a loop gives a correct total, while the same statement inside the loop wipes out the total on every pass.

Selection means the program chooses between different paths. An IF statement tests a condition and runs its statements only when the condition is true, with an optional ELSE clause for the other case. A CASE statement chooses between several branches depending on the value of one variable, and an OTHERWISE branch at the end catches anything that does not match.

Iteration means repeating statements, and there are three loops you must be able to tell apart. A count-controlled loop (FOR ... NEXT) repeats a known number of times. A pre-condition loop (WHILE ... DO ... ENDWHILE) tests its condition before the statements run, so it may run zero times. A post-condition loop (REPEAT ... UNTIL) tests its condition after the statements have run, so it always runs at least once.

In a flowchart the three constructs look different straight away. Sequence is a run of process boxes joined by arrows, selection is a diamond with two labelled exits, and iteration is a loop in which an arrow carries control back to a point earlier in the chart. There are six flowchart symbols you are expected to use, and they are listed in the table below.

Standard methods of solution: search, sort, totalling, counting and averages

Cambridge limits the standard methods of solution to six: linear search, bubble sort, totalling, counting, and finding maximum, minimum and average values. You need to recognise each one from its pseudocode, complete one that is partly written, and say what it does.

Totalling keeps a running total: the total is set to 0 before the loop and Total ← Total + Value sits inside it. Counting keeps a running count of how many items have been processed: the count is set to 0 before the loop and Count ← Count + 1 sits inside it. The two are often used together so that an average can be worked out as Total / Count.

Finding the maximum starts by setting the maximum to the first value in the list, then compares every remaining value with it and replaces the maximum whenever a larger value turns up. Finding the minimum is the same with the comparison reversed. Setting the maximum to 0 instead of to the first value is a classic error, because a list of negative numbers would leave the maximum sitting at 0.

A linear search checks each item in turn from the start until the item is found or the list runs out. It works on any list, sorted or not, but it is slow on a long list. A bubble sort puts a list into order by comparing neighbouring pairs and swapping them whenever they are in the wrong order, passing through the list again and again until a complete pass produces no swaps. Both of these are built out of the three constructs: a loop for the repetition, a selection for the comparison, and a sequence for the swap.

Validation, verification and test data

Validation is an automatic check made by the program as data is input, to test whether the data is sensible and allowed. It cannot tell whether the data is correct, only whether it is reasonable. A range check would accept 12/04/2009 as a date of birth for a Year 8 pupil even though it belongs to the wrong pupil, because it is a perfectly valid date.

Verification is a check that the data has been entered accurately, without being changed on the way in. It is about copying, not about sense. The two examinable methods are a visual check, where a person reads the data back and compares it with the source document, and a double entry check, where the data is typed in twice and the program compares the two versions, accepting the data only if they match.

The examinable validation checks are the range check, length check, type check, presence check, format check and check digit. A range check accepts only values between a lowest and a highest; a length check accepts only strings with the right number of characters; a type check accepts only data of the right type; a presence check refuses to accept a field that has been left empty; a format check insists on a particular pattern, such as dd/mm/yyyy for a date; and a check digit is a calculated extra digit added to a long number such as a barcode so that a single mistyped digit can be detected.

Test data has to be chosen deliberately. The four types are normal, abnormal, extreme and boundary data. Extreme data is the largest or smallest acceptable value, while boundary data is the largest or smallest acceptable value together with the corresponding smallest or largest rejected value. For a program that accepts an age from 11 to 18, extreme data would be 11 and 18, and boundary data would be 11 and 18 (which must be accepted) together with 10 and 19 (which must be rejected).

Dry runs, trace tables and finding errors

A dry run is working through an algorithm by hand, line by line, writing down the value of every variable as it changes. A trace table is how you record a dry run: one column for each variable, one row for each pass through the algorithm, and often a column showing what the algorithm outputs.

Work down the algorithm in order and write the value of a variable only after it has been changed. Leave a cell empty until that variable has a value, and never guess the final answer and work backwards: the marks are for the intermediate values as the algorithm runs. If a loop runs four times, the trace table needs four rows, and the output goes in its own row after the loop has finished.

The trace table below follows an algorithm that adds up only those scores of 50 or more, and counts how many of them there are. The four scores input are 40, 60, 70 and 30, and the algorithm outputs the value of Count once the loop has finished.

Dry runs are also the best way to find errors. The errors you will be asked about usually fall into a few types: a loop whose condition never becomes false, so the algorithm never finishes; a variable that is used before it has been given a value; a comparison written the wrong way round, so the algorithm takes the wrong branch; a loop that runs one time too many or one time too few; and an OUTPUT statement left inside a loop when it should sit after the loop, so the answer is printed several times.

When you are asked to suggest a correction, write the statement as it should be. 'Change the loop' earns nothing, but 'change UNTIL Count > 10 to UNTIL Count = 10' earns the mark, because the examiner can see exactly what you mean and where.