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"

---

Example 3: Tracing a Sorting Pass

Here is one pass of bubble sort on [5, 2, 8, 3]:

for i = 0 to 2
    if list[i] > list[i + 1] then
        temp = list[i]
        list[i] = list[i + 1]
        list[i + 1] = temp
    endif
next i

Trace table:

i	list[i]	list[i+1]	Swap?	List State
0	5	2	Yes	[2, 5, 8, 3]
1	5	8	No	[2, 5, 8, 3]
2	8	3	Yes	[2, 5, 3, 8]

---

Example 4: Tracing with Functions

function mystery(a, b)
    result = 0
    while b > 0
        result = result + a
        b = b - 1
    endwhile
    return result
endfunction

x = mystery(4, 3)
print(x)

Trace table:

Step	a	b	result	Output
Init	4	3	0
1	4	2	4
2	4	1	8
3	4	0	12
End				12

The function calculates 4 × 3 = 12 by repeated addition.

OCR Exam Tip: When a "mystery" function appears in the exam, use a trace table to work out what it does. After completing the trace, always state what the algorithm does in one sentence (e.g. "This function multiplies two numbers using repeated addition").

---

Common Trace Table Mistakes

Mistake	How to Avoid It
Forgetting to update a variable	Work through every line — do not skip steps
Confusing the loop condition	Check the condition BEFORE entering the loop body
Writing values in the wrong column	Label columns clearly and double-check
Miscounting array indices	Remember arrays start at index 0 in OCR pseudocode
Ignoring the output column	Always record what print() produces

---

Python Equivalents

The same trace table approach works for Python. Here is Example 1 in Python:

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

The trace table would be identical. The key difference is syntax, not logic.

---

Summary

• A trace table records variable values at each step of an algorithm.
• Columns represent variables (and an output column if needed).
• Rows represent steps or iterations.
• Trace tables are essential for understanding, debugging, and verifying algorithms.
• They are a very common exam question type on OCR J277 Paper 2.

OCR Exam Tip: In the exam, work slowly and carefully through trace tables. It is better to take an extra minute and get the right answer than to rush and make a mistake on the first step, which would make every subsequent answer wrong. If you have time, verify your trace by checking the final output makes sense.

---

Example 5: Nested Loops and an Array

Consider an algorithm that finds the minimum value in a list:

data = [7, 3, 9, 1, 5]
smallest = data[0]

for i = 1 to data.length - 1
    if data[i] < smallest then
        smallest = data[i]
    endif
next i

print(smallest)

Trace table:

Step	i	data[i]	smallest	data[i] < smallest?	Output
Init	—	—	7	—
1	1	3	3	Yes
2	2	9	3	No
3	3	1	1	Yes
4	4	5	1	No
End					1

The algorithm finds the smallest value in O(n) time by maintaining the running minimum.

---

Example 6: Tracing with Conditional Logic

Algorithms with several branches need careful trace tables. Consider:

mark = 72

if mark >= 70 then
    grade = "A"
elseif mark >= 60 then
    grade = "B"
elseif mark >= 50 then
    grade = "C"
else
    grade = "F"
endif

print("Grade: " + grade)

Trace table:

Step	mark	Condition tested	Result	grade	Output
Init	72	—	—	—
1	72	mark >= 70?	True	"A"
End					"Grade: A"

Note that in an if/elseif/else structure, only the first matching branch is executed. Once "A" is assigned, the other conditions are not evaluated.

---

Example 7: While Loop With Changing Condition

balance = 100
payment = 15
months = 0

while balance > 0
    balance = balance - payment
    months = months + 1
endwhile

print("Months to pay off: " + str(months))

Trace table: