1.4.1Trace tables

A trace table records the value of each variable after each step. It lets you find logic errors without a computer.

Trace of the Sum of 1 to N algorithm with N = 4:

The output is 10, which is correct (1 + 2 + 3 + 4).

Why trace?

When you read an algorithm, your brain fills in what you meant to write. A trace table makes you follow what is actually written, one step at a time, just as the computer will. Errors that you would never spot by reading become obvious when a value in the table is not the one you expected.

How to build a trace table

1. Make one column for each variable, one for each condition that is tested, and one for output.
2. Fill in the first row with the starting values (after the variables are first set).
3. Follow the algorithm one step at a time. Each time a variable changes, write its new value in a new row. Never skip a step "because it is obvious".
4. When a condition is tested, write true or false; this tells you which way the program goes.
5. When the algorithm ends, compare the output with the answer you worked out by hand.

Finding a logic error with a trace

Suppose the loop condition was written as i < N instead of i <= N. Trace it with N = 4:

The output is 6, but the correct answer is 10. The table shows exactly what went wrong: the loop stopped when i was 4, so 4 was never added. A single wrong character, < instead of <=, caused it. This is called an off-by-one error, and it is one of the most common logic errors in programming.

A trace with a decision

Algorithm: read three numbers and find the largest.

READ a, b, c
largest = a
IF b > largest THEN largest = b
IF c > largest THEN largest = c
PRINT largest

Trace with a = 4, b = 9, c = 7:

Now try (5, 5, 2) yourself: the answer should be 5. Equal values are a good test, because they check whether > or >= was the right choice.

Use the stepper below to watch a trace table being filled in, one pass at a time.