Algorithms

A recipe is an algorithm. So are directions to a friend's house. An algorithm is a list of steps that solves a problem. For a computer, it must be three things.

Before you can write an algorithm, you have to understand the problem. Computational thinking is four habits that turn a big, messy problem into clear steps.

Abstraction: the London Tube map

Before writing any algorithm, ask three questions. What goes in? What must happen? What comes out? Then build the "happen" part from only three kinds of block.

A flowchart draws an algorithm. Each shape means one kind of step. Arrows show what comes next. Learn the six symbols: exam boards use the same ones.

1. A decision always has two arrows out, labelled Yes and No.

2. A loop is an arrow going back up to an earlier step.

3. Exactly one Start. Every path must reach a Stop, or the algorithm isn't finite.

Here is one algorithm: count from 1 to 6 and say whether each number is odd or even. Below it is written four ways. Same plan, different spelling.

The trick for odd/even is the remainder. Divide by 2. Remainder 0 → even. Remainder 1 → odd. In pseudocode, the remainder is called MOD.

1. 7 ÷ 2 = 3 remainder 1. So 7 MOD 2 = 1 → odd.

2. 8 ÷ 2 = 4 remainder 0. So 8 MOD 2 = 0 → even.

3. Check 7: 3 × 2 + 1 = 7 ✓. Check 8: 4 × 2 + 0 = 8 ✓.

4. So the selection is: IF n MOD 2 = 0 THEN even ELSE odd. The remainder decides the path.

FOR n ← 1 TO 6
    IF n MOD 2 = 0 THEN
        OUTPUT n, " is even"
    ELSE
        OUTPUT n, " is odd"
    ENDIF
ENDFOR

for n = 1 to 6
    if n MOD 2 == 0 then
        print(str(n) + " is even")
    else
        print(str(n) + " is odd")
    endif
next n

This algorithm adds up 1 + 2 + … + n. Press Next and follow the glowing shape. Watch the variable boxes and the trace table fill in.

There are two kinds of iteration. A count-controlled loop knows how many times before it starts. A condition-controlled loop keeps going until something becomes true.

How many times does it repeat?

FOR loops in pseudocode include both ends. So FOR i ← 3 TO 7 runs for 3, 4, 5, 6, 7.

1. Rule: repeats = last − first + 1. The "+ 1" is because both ends count.

2. FOR i ← 3 TO 7: 7 − 3 + 1 = 5. Check by listing: 3, 4, 5, 6, 7. Five. ✓

3. FOR i ← 0 TO 9: 9 − 0 + 1 = 10.

4. With a STEP: FOR i ← 0 TO 20 STEP 5 → 0, 5, 10, 15, 20. (20 − 0) ÷ 5 + 1 = 5.

5. Loop inside a loop: repeat 4 with repeat 3 inside. The inside block runs 4 × 3 = 12 times.

6. Python is different: range(3, 7) stops before 7: 3, 4, 5, 6. That's 7 − 3 = 4 times. (Year 8.)

A variable is a named box that holds one value. Putting a new value in throws the old one away. In pseudocode the arrow ← means "put this value into this box".

1. Name it well. total, lives, guess. Not x, unless it really is just a number.

2. Give it a starting value before you use it: total ← 0. In Scratch: set total to 0 under the green flag. Forget it, and the old value from last time is still there.

3. A counter goes up by 1: count ← count + 1. A running total adds things up: total ← total + mark.

A trace table has one column for each variable. You go through the algorithm by hand, line by line, and write a new value every time one changes. This is called a dry run: running it on paper, not on a computer.

1numbers ← [7, 3, 12, 5]
2biggest ← numbers[0]
3FOR EACH n IN numbers
4    IF n > biggest THEN
5        biggest ← n
6    ENDIF
7ENDFOR
8OUTPUT biggest

numbers[0] means "item number 0", the first item. Lists count from 0.

Your turn, by hand

1x ← 1
2steps ← 0
3WHILE x < 20
4    x ← x × 3
5    steps ← steps + 1
6ENDWHILE
7OUTPUT steps, x

A dry run catches mistakes before the computer does. The most common one is being off by one: the loop runs once too many or once too few.

1i ← 1
2WHILE i < 5
3    OUTPUT i × 5
4    i ← i + 1
5ENDWHILE

Efficiency: how many steps?

Two algorithms can give the same answer, but one can take far fewer steps. To add up 1 + 2 + … + 100, you could loop 100 times. Or use the trick a young Carl Gauss is said to have spotted at school.

1. Write the sum forwards and backwards: 1 + 2 + … + 100 and 100 + 99 + … + 1.

2. Add them in pairs: 1 + 100 = 101, 2 + 99 = 101, … Every pair makes 101.

3. There are 100 pairs, so the two lists together make 100 × 101 = 10,100.

4. That's two copies of the sum, so halve it: 10,100 ÷ 2 = 5,050.

5. General rule: total = n × (n + 1) ÷ 2. That's 3 steps (×, +, ÷) whatever n is, instead of n additions.

The mistakes nearly everyone makes the first time. Read the left side, then the right.

Quick questions first. Then endless practice: a wrong answer shows you the working, step by step.