Using Trace Tables to Follow Algorithms

This lesson covers how to use trace tables to follow the execution of algorithms step by step, as required by OCR J277 Section 2.2. Trace tables are a fundamental tool for understanding, testing, and debugging algorithms, and they appear frequently in the OCR GCSE Computer Science exam.

---

What Is a Trace Table?

A trace table is a technique used to follow the execution of an algorithm by recording the values of variables at each step. Each row in the table represents one step (or iteration) of the algorithm, and each column represents a variable.

Trace tables help you to:

• Understand how an algorithm works by seeing the values change.
• Identify errors (bugs) in an algorithm by spotting where values go wrong.
• Predict the output of an algorithm without running it on a computer.
• Verify correctness of an algorithm by checking the final values.

OCR Exam Tip: Trace table questions are very common on Paper 2 and are typically worth 3–5 marks. They test your ability to follow pseudocode or Python code step by step. Accuracy is essential — one wrong value can lead to all subsequent values being wrong.

---

How to Create a Trace Table

1. Identify all variables in the algorithm — these become your column headings.
2. Add an Output column if the algorithm produces any output (e.g. using print()).
3. Work through the algorithm one line at a time.
4. When a variable's value changes, write the new value in the next row.
5. Continue until the algorithm terminates.

---

Example 1: Simple Loop

Consider this OCR pseudocode:

x = 1
total = 0
while x <= 5
    total = total + x
    x = x + 1
endwhile
print(total)

Trace table:

Step	x	total	Output
Init	1	0
1	2	1
2	3	3
3	4	6
4	5	10
5	6	15	15

The loop ends when x = 6 (since 6 > 5), and the output is 15 (the sum of 1+2+3+4+5).

---

Example 2: Tracing a Search Algorithm

Here is a linear search in OCR pseudocode:

data = [4, 7, 2, 9, 1]
target = 9
found = false
i = 0

while i < data.length AND found == false
    if data[i] == target then
        found = true
        print("Found at index " + str(i))
    endif
    i = i + 1
endwhile

if found == false then
    print("Not found")
endif

Trace table:

Step	i	data[i]	found	Output
Init	0	4	false
1	1	7	false
2	2	2	false
3	3	9	true	"Found at index 3"

---