Singapore-Cambridge A-Level Computing (H2)

Algorithms

An algorithm is a finite, ordered set of unambiguous steps that solves a problem or carries out a task. Given the same input it gives the same output, it ends after a finite number of steps, and each step is precise enough to be carried out without judgement. Writing the algorithm down before any code is written lets its logic be checked on its own, separately from the details of a programming language.

Every algorithm, however large, is built from three control structures.

• Sequence: statements run one after another, in the order written.
• Selection: a condition decides which statements run, using if, elif and else.
• Iteration: statements repeat, either while a condition holds (while) or for each item in a range or collection (for).

A program that finds the larger of two numbers uses sequence to read the numbers in, selection to compare them and sequence again to show the answer. A program that adds up the marks in a list uses iteration to visit each mark.

Pseudocode

Pseudocode describes an algorithm in structured, plain language, close enough to code to be translated easily but free of the syntax rules of any one language. There is no required syntax for it. What matters is that the logic is correct, that every step is unambiguous and that the layout shows which statements belong inside a selection or a loop, usually by indentation.

INPUT mark
IF mark >= 50 THEN
    OUTPUT "Pass"
ELSE
    OUTPUT "Fail"
ENDIF

The same averaging task, written with iteration, reads as follows.

total ← 0
count ← 0
FOR each mark IN marks
    total ← total + mark
    count ← count + 1
ENDFOR
IF count > 0 THEN
    average ← total / count
    OUTPUT average
ENDIF

The guard IF count > 0 is part of the logic: without it an empty list would divide by zero. Checking for cases like this, where the general steps break down, is a large part of designing an algorithm.

Python is close enough to pseudocode that many algorithms can be written directly in it, and the Python versions of the control structures are these.

# selection
if mark >= 70:
    grade = "A"
elif mark >= 50:
    grade = "B"
else:
    grade = "C"

# iteration with a count
for i in range(5):
    print(i)

# iteration with a condition
n = 27
steps = 0
while n != 1:
    n = n // 2 if n % 2 == 0 else 3 * n + 1
    steps += 1

range(5) produces 0, 1, 2, 3, 4, so the loop body runs five times. A while loop tests its condition before each pass, so its body may never run, and something inside the body has to move the loop towards ending or it will run for ever.

Choosing the loop

A for loop suits a known number of repetitions or a known collection to walk through. A while loop suits repetition until something happens, where the number of passes is not known in advance, such as asking for input until a valid value is entered.

password = input("Password: ")
while len(password) < 8:
    password = input("Too short, try again: ")

Nesting

Control structures can be placed inside one another. A loop can contain a selection, a selection can contain a loop, and a loop can contain another loop. The inner loop runs completely for every pass of the outer one, so two nested loops each of size $n$ run the innermost statement $n^2$ times.

for row in range(1, 4):
    for col in range(1, 4):
        print(row * col, end=" ")
    print()

This prints a three by three multiplication table, with end=" " keeping each row on one line.

Decomposition and the modular approach

Decomposition breaks a problem into smaller, more manageable sub-problems, each of which can be solved, written and tested separately. The solutions are then combined. In a program each sub-problem becomes a function or procedure, so the whole is a set of small modules and a main routine that calls them.

A program to process a class's test results might be decomposed into reading the data from a file, validating each mark, working out the average, finding the highest mark and printing a report. Each of these is small enough to understand at once. The benefits follow directly from that.

• Different people can write different modules at the same time.
• Each module can be tested alone before it is joined to the others.
• A module that works can be reused, in this program or another.
• A fault is easier to locate, because it is usually inside the module whose output is wrong.
• A change to how one task is done touches one module instead of the whole program.

Decomposition also shows up as top-down design: start with the whole task at the top, split it into its main parts, then split each part again until every piece is simple enough to write directly.

The incremental approach

The incremental approach solves a small version of the problem first, then extends the solution step by step to cover larger versions. To sort a list of any length, for example, first write something that sorts two items, then three, and notice what stays the same as the list grows. To read a full set of student records, first read and display one record correctly, then a loop over several, then the handling of a missing value.

Each increment can be run and checked before the next is added, so when a fault appears it must lie in the newest piece. The approach also tends to find the general pattern that an algorithm needs, and it fits well with testing, since a program that has grown by small working steps always has a version that runs.

Devising algorithms and tracing them

To devise an algorithm, state what the input is and what output is wanted, work a small example by hand, write down the steps that were taken, and then generalise them with variables, loops and conditions. The algorithm is then tested on inputs that include awkward cases: an empty list, a single item, equal values, the largest and smallest allowed values.

Finding the largest value in a non-empty list shows the pattern.

def largest(values):
    biggest = values[0]
    for v in values[1:]:
        if v > biggest:
            biggest = v
    return biggest

Starting biggest at the first item, instead of at 0, is what makes the function correct for a list of negative numbers. A hand trace for [4, 9, 2, 7] runs: biggest is 4; 9 is bigger, so it becomes 9; 2 is not; 7 is not; the result is 9.