Trace tables

Following an algorithm line by line, and tracing to find a logic error.

F5.4AlgorithmsGCSE15 min

A program that runs without an error can still be wrong. To find out what an algorithm really does, programmers trace it: follow it line by line, by hand, writing down the value of every variable each time it changes. A trace table is where you write it down. It is how you check an algorithm before trusting it, and how exams test whether you understand one.

A first trace

total = 0
for i in range(1, 5):
    total = total + i * 2
print(total)

One column per variable, plus a column for output. A new row every time something changes:

Work through it yourself on paper first, then run the program to check:

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

total = 0
for i in range(1, 5):
    total = total + i * 2
print(total)

Run this in the simulator

Let the program trace itself

Adding a print inside the loop makes the program write its own trace table. This is exactly how programmers debug:

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

x = 1
y = 10
print("x", "y")
while x < y:
    x = x * 2
    y = y - 1
    print(x, y)
print("finished with x =", x)

Run this in the simulator

Before you run it, trace it on paper. When does the loop stop, and why? Then run it and compare row by row. The first row where your table and the program disagree is where your understanding and the algorithm part company.

The Debug button does the same job on screen: it stops at each line and shows the variables as they change.

Tracing to find a bug

This program should give the average of five distance readings, 40, 35, 30, 25 and 20, which is 30. It prints something else:

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

readings = [40, 35, 30, 25, 20]
for i in range(len(readings)):
    total = 0
    total = total + readings[i]
print("average:", total / len(readings))

Run this in the simulator

It prints average: 4.0. No error message, so this is a logic error. A trace shows it straight away:

total never grows. It goes back to 0 every time round, because total = 0 is inside the loop. By the end, total holds only the last reading, 20, and 20 divided by 5 is 4.0.

Tracing a robot

The robot's position can go in a trace table too. Predict where this program leaves the robot, then run it:

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

side = 10
for i in range(3):
    forward(60, distance=side)
    right(60, distance=side)
    side = side + 5
print("at", position())

Run this in the simulator

So it should end 45 cm up and 45 cm right. The robot's own report will be close but not exact, because a real (or simulated) robot drifts a little.

Task: trace and fix

Fix the average program so it prints average: 30.0. Keep a trace: inside the loop, print a line i=<i> total=<total> each time round, so the program shows its own trace table.

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

readings = [40, 35, 30, 25, 20]
for i in range(len(readings)):
    total = 0
    total = total + readings[i]
print("average:", total / len(readings))

Challenges

1. Trace n = 27 then while n != 1: if n is even, n = n // 2, else n = 3 * n + 1 for the first six rows. Then run it to see how long it really takes.
2. Write a trace table for the parking sensor's loop, with the distance, the gap and the beep count.
3. Swap the two lines inside the x and y loop above. Trace it again before running. Does it still stop?