CS5: Trace Tables
Using trace tables to step through algorithms, track variable values, and identify the purpose of unknown algorithms.
📋 What is a Trace Table?
Definition: A trace table is a table used to record the value of variables each time they change as an algorithm is executed step by step. It helps you understand how an algorithm works, find logic errors, and determine what an unknown algorithm does.
Trace tables are essential for:
- Understanding how an algorithm processes data step by step
- Testing algorithms with different inputs (dry running)
- Finding logic errors by comparing expected vs actual values
- Identifying the purpose of unfamiliar algorithms
📝 Setting Up a Trace Table
Setting up a trace table: Create a column for each variable in the algorithm, plus a column for any OUTPUT statements. Each row represents one execution step where a variable changes.
Rules for Trace Tables:
1. One column per variable + one for OUTPUT
2. Each row = one step where a variable changes
3. Only record a value when it changes
4. Leave cells blank if a variable doesn't change in that step
5. Record outputs in the OUTPUT column when they occur
1. One column per variable + one for OUTPUT
2. Each row = one step where a variable changes
3. Only record a value when it changes
4. Leave cells blank if a variable doesn't change in that step
5. Record outputs in the OUTPUT column when they occur
Basic Trace Table Setup
For an algorithm with variables x, y, and total:
| Step | x | y | total | OUTPUT |
|---|---|---|---|---|
| Initial | - | - | - | - |
🔢 Stepping Through Algorithms
Example 1: Simple Counter
Algorithm
count ← 0
total ← 0
FOR i ← 1 TO 4
count ← count + 1
total ← total + i * 2
NEXT i
OUTPUT total
Trace Table
| Iteration | i | count | total | OUTPUT |
|---|---|---|---|---|
| Initial | - | 0 | 0 | - |
| 1 | 1 | 1 | 2 | - |
| 2 | 2 | 2 | 6 | - |
| 3 | 3 | 3 | 12 | - |
| 4 | 4 | 4 | 20 | - |
| End | - | - | - | 20 |
Explanation: total accumulates 2 + 4 + 6 + 8 = 20
Example 2: Finding the Maximum
Algorithm
numbers ← [3, 7, 2, 9, 5]
max ← numbers[0]
FOR i ← 1 TO 4
IF numbers[i] > max THEN
max ← numbers[i]
ENDIF
NEXT i
OUTPUT max
Trace Table
| Iteration | i | numbers[i] | max | OUTPUT |
|---|---|---|---|---|
| Initial | - | - | 3 | - |
| 1 | 1 | 7 | 7 | - |
| 2 | 2 | 2 | 7 | - |
| 3 | 3 | 9 | 9 | - |
| 4 | 4 | 5 | 9 | - |
| End | - | - | - | 9 |
Explanation: The algorithm finds the maximum value in the array. When numbers[i] > max, the new max is recorded.
Example 3: WHILE Loop with Condition
Algorithm
num ← 10
WHILE num > 1
IF num MOD 2 = 0 THEN
num ← num DIV 2
ELSE
num ← num * 3 + 1
ENDIF
ENDWHILE
OUTPUT num
Trace Table
| Step | num (before) | Condition | Action | num (after) | OUTPUT |
|---|---|---|---|---|---|
| 1 | 10 | 10 > 1: TRUE, 10 MOD 2 = 0 | num ← 10 DIV 2 | 5 | - |
| 2 | 5 | 5 > 1: TRUE, 5 MOD 2 ≠ 0 | num ← 5*3+1 | 16 | - |
| 3 | 16 | 16 > 1: TRUE, 16 MOD 2 = 0 | num ← 16 DIV 2 | 8 | - |
| 4 | 8 | 8 > 1: TRUE, 8 MOD 2 = 0 | num ← 8 DIV 2 | 4 | - |
| 5 | 4 | 4 > 1: TRUE, 4 MOD 2 = 0 | num ← 4 DIV 2 | 2 | - |
| 6 | 2 | 2 > 1: TRUE, 2 MOD 2 = 0 | num ← 2 DIV 2 | 1 | - |
| 7 | 1 | 1 > 1: FALSE | Exit loop | - | 1 |
This is the Collatz sequence! The algorithm halves even numbers and triples+1 odd numbers until reaching 1.
🔎 Identifying the Purpose of Unknown Algorithms
Exam technique: When given an unknown algorithm, create a trace table and look at the pattern of values. The OUTPUT and how variables change will reveal what the algorithm does.
What does this algorithm do?
x ← 17
y ← 5
WHILE x >= y
x ← x - y
ENDWHILE
OUTPUT x
| Step | x | y | x >= y? |
|---|---|---|---|
| 1 | 12 | 5 | TRUE |
| 2 | 7 | 5 | TRUE |
| 3 | 2 | 5 | FALSE → exit |
OUTPUT: 2
Purpose: This calculates the remainder when x is divided by y (the MOD operation). 17 MOD 5 = 2. It repeatedly subtracts y from x until x < y.
What does this algorithm do?
result ← 1
FOR i ← 1 TO 5
result ← result * i
NEXT i
OUTPUT result
| i | result |
|---|---|
| - | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
OUTPUT: 120
Purpose: This calculates 5 factorial (5!) = 1 × 2 × 3 × 4 × 5 = 120.
👁️ Visual Inspection of Trace Tables
Tip: When looking at a completed trace table, examine the OUTPUT column and look for patterns in how variables change. Common patterns include: counting, accumulating (sum), finding maximum/minimum, searching, and computing remainders.
| Pattern in Variables | What the Algorithm is Doing |
|---|---|
| One variable increases by 1 each step | Counting |
| One variable adds another variable each step | Accumulating / calculating a total |
| A variable is replaced only when a new value is larger | Finding the maximum |
| A variable is replaced only when a new value is smaller | Finding the minimum |
| A variable is multiplied by another each step | Calculating a product / factorial / power |
| A variable decreases by repeated subtraction | Division or MOD operation |
🐛 Using Trace Tables for Debugging
Finding the Error
This algorithm is supposed to calculate the average of 3 numbers, but it gives the wrong answer:
total ← 0 INPUT a INPUT b INPUT c total ← a + b + c average ← total / 2 OUTPUT average
Input: a = 10, b = 20, c = 30
| Variable | Expected | Actual |
|---|---|---|
| total | 60 | 60 |
| average | 20 | 30 |
Error found: The algorithm divides by 2 instead of 3. The line should be average ← total / 3.
⚠️ Common Mistakes
| Mistake | Why It's Wrong | How to Fix It |
|---|---|---|
| Not recording initial values | You need the starting point to trace correctly | Always fill in initial variable values before the loop |
| Recording values that don't change | It clutters the table and wastes time | Only fill in a cell when the variable actually changes |
| Missing an iteration | Your trace will be incomplete and give wrong results | Check FOR loop bounds carefully - count each iteration |
| Wrong operator (DIV vs /) | Integer division gives different results from real division | Use DIV for integer division, / for real division |
| Not evaluating conditions properly | IF conditions may or may not execute their body | Always evaluate the condition and record whether it was TRUE or FALSE |
❓ Practice Questions
Q1: Complete a trace table for this algorithm with input num = 7:
result ← 0
FOR i ← 1 TO num
result ← result + i
NEXT i
OUTPUT result
Q2: What does the following algorithm compute? Use a trace table with x = 24, y = 6.
count ← 0
WHILE x >= y
x ← x - y
count ← count + 1
ENDWHILE
OUTPUT count
Q3: Complete a trace table for the following algorithm with the array [4, 1, 8, 3]:
min ← numbers[0]
FOR i ← 1 TO 3
IF numbers[i] < min THEN
min ← numbers[i]
ENDIF
NEXT i
OUTPUT min
Q4: Explain why trace tables are useful for debugging.
Q5: A trace table shows a variable that increases by 1 each iteration. What is the algorithm most likely doing?
✅ Answers
-
OUTPUT: 28 (This calculates the sum 1+2+3+4+5+6+7 = 28)i result - 0 1 1 2 3 3 6 4 10 5 15 6 21 7 28 - The algorithm counts how many times y fits into x - it performs integer division (24 DIV 6 = 4). The OUTPUT is 4.
- Initial: min = 4. i=1: numbers[1]=1, 1<4, min=1. i=2: numbers[2]=8, 8>1, no change. i=3: numbers[3]=3, 3>1, no change. OUTPUT: 1 (the minimum value).
- Trace tables let you step through an algorithm line by line, recording variable values. This allows you to compare what you expected to happen with what actually happens, making it easy to spot where a logic error occurs.
- It is most likely counting. A variable that increments by 1 each step is typically a counter.
🎯 Exam Tips
- Always set up columns before you start tracing - include every variable and an OUTPUT column
- Record initial values before the loop begins
- Go through the algorithm line by line - don't skip steps
- For IF statements, evaluate the condition and only update variables if the condition is TRUE
- When asked "what does this algorithm do?", trace it first then describe the overall purpose
- Double-check your arithmetic - one wrong calculation will throw off the rest of the table
- If asked to find an error, trace the algorithm and compare with what should happen
⚠️ Common Errors
✗ Leaving columns out of a trace table because the variable 'doesn't change' ✓ Every variable used in the algorithm must have its own column in the trace table, even if its value doesn't change — you still record the initial value.
✗ Recording output values inside variable columns instead of noting them separately ✓ Outputs should be recorded as they occur, often in a separate 'OUTPUT' column or noted at the side; they are not stored in variables unless explicitly assigned.
✗ Only recording variable values at the end rather than after each iteration ✓ A trace table must show how variable values change after each step or loop iteration, not just the final values — this is how you debug algorithms.
✗ Forgetting to update the loop counter in a trace table ✓ The loop counter (e.g. 'counter' in a FOR loop) must be updated in the trace table each iteration, as it controls when the loop terminates.
✍️ Model Answer
Full-Mark Response
The following pseudo-code processes an array: FOR i ← 1 TO 4 IF numbers[i] > max THEN max ← numbers[i] ENDIF NEXT i. Given numbers = [3, 7, 2, 9] and max = 0 initially, complete a trace table showing the value of i, numbers[i], max and the condition result for each iteration. [5 marks]
Iteration | i | numbers[i] | Condition (numbers[i] > max) | max after 1 | 1 | 3 | 3 > 0 = TRUE | 3 2 | 2 | 7 | 7 > 3 = TRUE | 7 3 | 3 | 2 | 2 > 7 = FALSE | 7 4 | 4 | 9 | 9 > 7 = TRUE | 9 The algorithm finds the maximum value in the array. After all iterations, max = 9.
📊 AO Deep Dive
Assessment Objective Analysis
AO1 (Computational Thinking — 40%): Demonstrate knowledge and understanding of the principles and concepts of computer science, including trace tables and dry-running algorithms for AQA 8525, OCR J277 & Edexcel 1CP2.
AO2 (Application — 40%): Apply knowledge and understanding of computer science, including trace tables and dry-running algorithms to analyse problems in computational terms and to design, write and evaluate solutions.
AO3 (Evaluation — 20%): Evaluate the effectiveness, correctness and efficiency of computational solutions, including trace tables and dry-running algorithms, and make reasoned judgements about trade-offs.
📝 Exam Technique
GCSE Computer Science Exam Tips:
Always create a column for EVERY variable in the algorithm, plus any output. Update values row by row as each line of code executes. For loops, record each iteration separately. For IF statements, show the condition evaluation (TRUE/FALSE). Don't skip rows even if a variable doesn't change — write the same value. If asked to find an error in code, completing a trace table will reveal where the logic goes wrong.
Always create a column for EVERY variable in the algorithm, plus any output. Update values row by row as each line of code executes. For loops, record each iteration separately. For IF statements, show the condition evaluation (TRUE/FALSE). Don't skip rows even if a variable doesn't change — write the same value. If asked to find an error in code, completing a trace table will reveal where the logic goes wrong.
📝 Exam Questions by Topic
🎬 Video Resources
Ready to ace your GCSE Computer Science exams?
Get the best revision books and guides to boost your grades.