A trace table records the value of every variable after each step, so you can prove what an algorithm does instead of guessing. It appears whenever a question gives pseudocode and asks for the output or for the values at a certain point.
It builds on defining inputs and outputs, and leads into designing selections with boundary cases, where a trace shows which branch ran.
How do you build a trace table?
- Make a column for each variable, for any condition you want to show, and for output.
- Write the starting values in the first row, before any loop pass.
- Work through the algorithm one line at a time. When a variable changes, write its new value in the next row. Copy unchanged values down.
- Record output at the moment OUTPUT runs.
- Check the stopping point: know why the loop ended.
Worked example
Trace this algorithm and give its output.
Total ← 0
Count ← 0
FOR N ← 1 TO 5
IF N MOD 2 = 1 THEN
Total ← Total + N
Count ← Count + 1
ENDIF
NEXT N
OUTPUT Total, CountStep 1, columns and start: N, N MOD 2, Total, Count. Start with Total = 0 and Count = 0.
Step 2, one row per pass:
| N | N MOD 2 | Total | Count |
|---|---|---|---|
| start | 0 | 0 | |
| 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 |
| 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 2 |
| 5 | 1 | 9 | 3 |
Step 3, output: the loop ends after N = 5, so the output is 9, 3.
Check: the odd numbers from 1 to 5 are 1, 3 and 5. Their sum is 9 and there are 3 of them. This matches the table.
The mistake to watch for
A common slip is to skip the starting row and the rows where nothing changes.
Mistaken trace: the student writes only the rows for N = 1, 3 and 5, and begins with Total = 1.
The table looks tidy, but it no longer proves that the even values were tested and left alone.
The correction is to include the starting row and a row for every pass, even when the values are copied down. If the algorithm had a fault in the IF condition, such as N MOD 2 = 0 by mistake, the missing rows would hide it. The full table shows which test failed.
Check yourself
1. Trace this and give the output.
X ← 3
Y ← 10
WHILE Y > X DO
Y ← Y - X
X ← X + 1
ENDWHILE
OUTPUT X, YShow answer
Start X = 3, Y = 10. Test 10 > 3 is true: Y = 7, X = 4. Test 7 > 4 is true: Y = 3, X = 5. Test 3 > 5 is false, so the loop stops. Output 5, 3.
2. What is the output?
S ← 0
FOR I ← 2 TO 8 STEP 2
S ← S + I
NEXT I
OUTPUT SShow answer
I takes the values 2, 4, 6, 8. S is 2, then 6, then 12, then 20. Output 20.
3. In the worked example, change the condition to N MOD 2 = 0. What is the output?
Show answer
Now N = 2 and N = 4 are counted. Total = 2 + 4 = 6 and Count = 2. Output 6, 2.
Where this leads next
Next, apply tracing to selection with boundary cases. Practise on small original algorithms in the pseudocode trace trainer, which shows each variable changing and the branch that ran.
A trace is only as good as the care behind it, and a teacher can check your tables line by line in online one-to-one Computer Science tuition. The practice set includes several traces.