Tracing flowcharts

An algorithm written as numbered steps is easy to write and hard to see. A flowchart draws the same algorithm as boxes and arrows, so the decisions and the loops stand out as shapes. It is also the quickest way to check that an algorithm does what you think, because you can follow it with a finger, one box at a time. Doing that carefully, and writing down what happens to every variable, is called tracing.

Flowcharts use a small set of standard shapes, so that anyone can read someone else's chart. A chart runs from the top of the page downwards, and from left to right.

A decision box must hold a question that can only be answered yes or no, with each exit labelled. A loop is nothing special in a flowchart: it is an arrow that goes back to a box above it, usually to a decision. A subroutine (a named block of steps defined elsewhere) is drawn as one box and is traced as one step, then its own chart is followed separately.

A trace table is a table with a column for each variable (and one for output). Doing it on paper with chosen values is a dry run. The method never changes:

1. Make a column for every variable, plus one for output.
2. Start at the Start box. Write down any starting values the chart sets.
3. Follow the arrows one box at a time. For a process, work out the new value from the current values and write it in a new row.
4. For a decision, test the condition with the current values and follow the matching exit. Write down the answer if it helps.
5. Keep going until you reach End. Read the output off the table.

Here is the loop that you will meet in the first chart below, traced by the same engine that drives the figure. A starts at 10 and goes up in tens, and B starts at 100 and goes down in tens. The loop stops as soon as A is no smaller than B.

The loop body ran 5 times: the test A ≥ B was false after passes 0 to 4 and true after pass 5, where A = 60 and B = 50. The condition was tested six times, one more than the body ran. Mixing up those two numbers is the most common way to lose marks on a counting question.

Many algorithms ask for input inside the loop. In the guessing game the loop reads a guess, tests it, and goes back if it was wrong; each trip round reads the next value from the player. When you trace one, write the inputs down in order beforehand, and cross each off as it is used, so that you cannot read the same one twice.

The digit-sum chart uses two operators that exam questions love. N MOD 10 is the remainder after dividing by 10, which is the last digit; N DIV 10 is the whole-number result of dividing by 10, which chops that digit off. Starting from 472 the loop adds 2, then 7, then 4, and stops when N reaches 0.

The second chart in the figure is a linear search, the simplest way to find something in a list: look at the first item, then the next, and stop when you find it or run out. Try the three starting targets. The one at the end of the array takes the longest to find, and the one that is not there takes just as long to give up on. That is the cost you will put a name to in B2.4, and the trace table is how you count it.