Trace tables

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

F13.2Exam preparationGCSE15 min

"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.

The three slips that cost marks: changing two variables on one row, forgetting the check that ends the loop, and starting the loop body before testing the condition.

An example, by hand

total = 0
count = 1
WHILE count <= 3
    total = total + count
    count = count + 1
ENDWHILE
OUTPUT total

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.

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.

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.