Using Trace Tables

A trace table is a technique used to track the values of variables as an algorithm executes, step by step. Trace tables are an essential tool for testing, debugging, and understanding how an algorithm works.

---

Why Use Trace Tables?

Trace tables help you:

• Understand how an algorithm works by following it through step by step
• Find errors (bugs) in an algorithm by checking whether the output is correct
• Predict the output of an algorithm for a given input
• Verify correctness — check that an algorithm produces the expected results

They are frequently tested in GCSE exams. You will often be given pseudocode or a flowchart and asked to complete a trace table.

---

How to Create a Trace Table

1. Create columns — one for each variable in the algorithm, plus one for any output.
2. Work through the algorithm line by line.
3. Update the table whenever a variable changes value.
4. Record output in the output column whenever a PRINT or OUTPUT statement is reached.

The flow of values through code, captured by a trace table, looks like this:

graph TD
    A["Read next line of code"] --> B{"Is it an assignment?"}
    B -->|Yes| C["Update variable column"]
    B -->|No| D{"Is it OUTPUT?"}
    D -->|Yes| E["Add value to Output column"]
    D -->|No| F{"Is it a loop/IF?"}
    F -->|Yes| G["Evaluate condition"]
    F -->|No| H["Carry values forward"]
    C --> I["Move to next line"]
    E --> I
    G --> I
    H --> I

---

Example 1: Simple Loop

x = 0
FOR i = 1 TO 5
    x = x + i
NEXT i
OUTPUT x

Trace Table:

Step	i	x	Output
Initial	—	0
1	1	1
2	2	3
3	3	6
4	4	10
5	5	15
End	—	15	15

The algorithm calculates the sum of numbers from 1 to 5 (1 + 2 + 3 + 4 + 5 = 15).

---

Example 2: IF Statement Inside a Loop

total = 0
count = 0
numbers = [4, 7, 2, 9, 1]
FOR i = 0 TO 4
    IF numbers[i] > 3 THEN
        total = total + numbers[i]
        count = count + 1
    ENDIF
NEXT i
OUTPUT total
OUTPUT count

Trace Table:

Step	i	numbers[i]	numbers[i] > 3?	total	count	Output
Initial	—	—	—	0	0
1	0	4	Yes	4	1
2	1	7	Yes	11	2
3	2	2	No	11	2
4	3	9	Yes	20	3
5	4	1	No	20	3
End	—	—	—	20	3	20, 3

The algorithm finds the total and count of numbers greater than 3.

---

Example 3: WHILE Loop

n = 100
count = 0
WHILE n > 1
    n = n DIV 2
    count = count + 1
ENDWHILE
OUTPUT count

Trace Table:

Step	n	n > 1?	count	Output
Initial	100	—	0
1	50	Yes	1
2	25	Yes	2
3	12	Yes	3
4	6	Yes	4
5	3	Yes	5
6	1	Yes	6
End	1	No	6	6

The algorithm counts how many times 100 can be halved (using integer division) before reaching 1. The answer is 6.

---

Example 4: Tracing a Bubble Sort Pass

list = [5, 3, 8, 1]
FOR j = 0 TO 2
    IF list[j] > list[j + 1] THEN
        temp = list[j]
        list[j] = list[j + 1]
        list[j + 1] = temp
    ENDIF
NEXT j

Trace Table:

j	list[j]	list[j+1]	Swap?	temp	List After
0	5	3	Yes	5	[3, 5, 8, 1]
1	5	8	No	—	[3, 5, 8, 1]
2	8	1	Yes	8	[3, 5, 1, 8]

After one pass: [3, 5, 1, 8]

---

Tips for Completing Trace Tables in Exams

1. Read the algorithm carefully before starting — understand the overall purpose.
2. Create all columns first — include every variable, plus an output column.
3. Go line by line — do not skip steps, even if you think you know the answer.
4. Only update a cell when the variable actually changes — leave it blank or carry forward the previous value otherwise.
5. Be careful with loop conditions — check whether the condition is still true before executing the loop body.
6. Check array indices — remember that most arrays start at index 0.
7. Show all working — even if the algorithm is simple, the examiner wants to see your trace.

Exam Tip: In GCSE exams, you will score marks for each correctly traced row. Even if you make an error partway through, you can still gain marks for subsequent rows if you follow through correctly from your (incorrect) values. This is called "error carried forward" (ECF). So always complete the entire trace table.

---

Common Mistakes to Avoid

• Forgetting to initialise variables — always show the initial values before the loop starts
• Off-by-one errors — check whether loops are 0 TO n-1 or 1 TO n
• Not updating the output column — only write in the output column when there is an OUTPUT/PRINT statement
• Confusing DIV and / — DIV gives integer division (truncates), / gives normal division
• Skipping the loop termination check — show the step where the loop condition becomes false

---

Key Points

• A trace table tracks variable values step by step as an algorithm executes.
• Create one column per variable plus an output column.
• Work through the algorithm line by line, updating values as they change.
• Trace tables are used to test, debug, and understand algorithms.
• Always complete the entire trace table in an exam, even if you spot an error.

---

Extended Worked Examples

Worked Example A: Trace a Complete Bubble Sort Pass with Comparisons

Trace the following algorithm on list = [4, 1, 3, 2]:

list = [4, 1, 3, 2]
n = 4
FOR i = 0 TO n - 2
    FOR j = 0 TO n - 2 - i
        IF list[j] > list[j+1] THEN
            temp = list[j]
            list[j] = list[j+1]
            list[j+1] = temp
        ENDIF
    NEXT j
NEXT i
OUTPUT list