Trace tables

Being the computer: a row for every change, and the checks that catch a slip.

F13.2Exam preparationGCSE15 min

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Trace tables explained

"Complete the trace table" is on every paper, and it is one of the few questions where you can be certain you are right before you move on. You are given an algorithm and asked to be the computer: follow it line by line and write down what every variable holds. This lesson is the method, and a program that does it with you.

The method

  1. Draw a column for every variable, plus one for anything printed.
  2. Write the starting values in the first row.
  3. Go through the algorithm one line at a time, in the order the computer would.
  4. Every time a variable changes, write the new value on a new row, under its column. Never rub anything out: the examiner wants the history.
  5. At a loop, check the condition each time round and write the result.

If the question gives you a table, follow its layout: some have a row for every change, some a row for each time round the loop, as in lesson F5.4. The marks are for the right values in the right order, so either earns them when the values are right. With no table given, a new row for every change is the safest.

The two slips that cost marks: forgetting the check that ends the loop, and starting the loop body before testing the condition.

The lesson's WHILE loop as a flowchart, with the two slips that cost marks marked where they happentotal = 0count = 1count <= 3 ?total = total + countcount = count + 1truefalseOUTPUT totalslip 1: leaving out this lastcheck, when count is 4and the answer is falseslip 2: doing these two linesbefore the check above them
Every time round, the question comes before the two lines inside the loop. The loop only ends when the answer is false, with count at 4, and that false check is a row of the table too.

An example, by hand

total = 0
count = 1
WHILE count <= 3
    total = total + count
    count = count + 1
ENDWHILE
OUTPUT total
count total count <= 3 output
1 0
1 true
2
3 true
3
6 true
4
false 6

The same trace, printed

A program can keep the table for you, which is a good way to check your own by hand:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

total = 0
count = 1
print("count total condition")
while count <= 3:
    print(f"{count:5} {total:5} {'true':>9}")
    total = total + count
    count = count + 1
print(f"{count:5} {total:5} {'false':>9}")
print("output:", total)

Run this in the simulator

Reading a trace like this is also how you find a bug: the row where the numbers stop matching what you expected is the line that is wrong.

To check a table you have filled in, trace() will fill one in too. Name the variables, in quotes, and it writes a row every time one of them changes, headed by the line that changed it:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

# watch count and total: a new row every time one of them changes
trace("count", "total")
total = 0
count = 1
while count <= 3:
    total = total + count
    count = count + 1
print("output:", total)

Run this in the simulator

It gives the same values in the same order as the table you did by hand above, one change per row, with the line numbers of this program. The only difference is the start: the hand table puts the two starting values on one row, and trace() gives each its own. It does not write the condition column: that part is yours.

Watch for these

  • A loop that runs one time too many or too few: check the condition at the boundary, < against <=.
  • A variable reset inside the loop when it should have been set before it.
  • Integer division: 7 // 2 is 3, not 3.5.
  • The value a variable holds when the loop ends, which is usually one past the last one used.
The loop's checks for count 1 to 4 with count <= 3 and with count < 3count1234WHILE count <= 3truetruetruefalsebody runs 3 timesoutput 6WHILE count < 3truetruefalsebody runs 2 timesoutput 3count 3 is never addedWith <= 3 the loop ends with count at 4: one past the last one used.
One character changes the answer. With < the check is already false at 3, so the last value is missed. Either way the loop ends on a false check, and count is left one past the last value used.

Task: print the trace

Trace the algorithm in the comment by running it, printing one line per row in the form n=<n> total=<total> check=<true or false>, in the order the computer reaches them. Print the check as true while the loop keeps going and false on the row that ends it. Finish with output: <total>.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

# total = 0
# n = 5
# WHILE n > 1
#     total = total + n
#     n = n - 2
# ENDWHILE
# OUTPUT total
total = 0
n = 5

Challenges

  1. Change the loop to n >= 1. Which extra row appears?
  2. Trace it by hand first, then run it. Did your table match?
  3. Write a trace for a for loop over range(3), showing the loop variable each time.

Past paper questions on this

Real exam questions that test this, each worked through with a program you can run.