A trace table lets you run through an algorithm by hand and record what a computer would do: how each variable changes, what each condition gives and what is output. Working through code by hand like this is called a dry run.
Reason 1: to find out what an algorithm does. Run it with some inputs and look at what happens.
Reason 2: to check its logic for errors that aren’t easy to spot by reading.
You can also work out what simple code does by visual inspection: reading it carefully and recognising patterns (see “Determining the purpose”).
Trace questions appear on every Paper 1, worth 6 to 15 marks in total.
Worked exampleThis algorithm should output the highest of three temperatures. Trace it to find the error.
temps ← [-3, -8, -1]
highest ← 0
FOR i ← 0 TO 2
IF temps[i] > highest THEN
highest ← temps[i]
ENDIF
ENDFOR
OUTPUT highest
highest starts at 0the first value is set before the loop
i = 0: −3 > 0 is False. i = 1: −8 > 0 is False. i = 2: −1 > 0 is Falsehighest never changes
OUTPUT 0but 0 isn’t one of the temperatures; the highest is −1
The trace shows a logic error: highest should start at temps[0], not 0. (Correcting errors is covered in the topic on testing and errors.)
Trace table
A table with a column for each variable (and outputs or conditions), used to record their values as an algorithm is run by hand.
Dry run
Working through an algorithm by hand, step by step, without a computer.
Visual inspection
Reading an algorithm carefully to work out what it does, without tracing every step.
3.1.1 Determine the purpose of simple algorithms
Setting up and filling in a trace table
One column per variable, usually in the order they are first met. Add an OUTPUT column, and a column for a condition (True/False) if the question gives one.
Write a value only when it changes. Leave the other cells blank.
Work line by line. Time runs left to right and top to bottom, like reading a page.
To find a variable’s current value, look up its column to the last value written.
Move to a new row when you go round a loop again, or when a column you need already has a value in the current row.
One column per variable; time runs down the table
Worked exampleTrace the algorithm in the diagram.
n = 3, total = 0first row: the starting values
3 > 0 True: total = 0 + 3 = 3, n = 2first time round the loop
2 > 0 True: total = 5, n = 1. 1 > 0 True: total = 6, n = 0two more passes
0 > 0 False: the loop ends. OUTPUT 6the output appears once, after the loop
Output: 6
Exam tipAQA’s mark schemes don’t mind which row a value is on, as long as the order within each column is right, and they ignore a value repeated on the next row. They do penalise extra values that shouldn’t be there.
3.1.1 Determine the purpose of simple algorithms
Tracing sequence and selection
Run each line in order. At an IF, work out the condition using the current values, then follow only the branch it picks.
In IF … ELSE IF … ELSE … ENDIF, the conditions are checked from the top. The first one that is True runs, and the rest are skipped. If none is True, the ELSE runs.
So exactly one branch runs each time.
Watch the boundaries: hours > 4 is False when hours is 4; hours ≥ 4 is True.
Worked exampleComplete the table of outputs for this bike-hire algorithm.
hours ← USERINPUT
member ← USERINPUT
IF hours > 4 THEN
cost ← 20
ELSE IF member = 'Y' THEN
cost ← hours * 3
ELSE
cost ← hours * 4
ENDIF
OUTPUT cost
hours 5, member N: 5 > 4 True, so cost ← 20the first condition wins
hours 2, member Y: 2 > 4 False; member = 'Y' True, so cost ← 6second branch
hours 4, member N: 4 > 4 False; 'N' = 'Y' False, so ELSE: cost ← 164 is not more than 4
hours 6, member Y: 6 > 4 True, so cost ← 20member is never checked
hours
member
Output
5
N
20
2
Y
6
4
N
16
6
Y
20
3.1.1 Determine the purpose of simple algorithms
Tracing loops: FOR, WHILE, REPEAT…UNTIL and nested loops
Loop
When the condition is checked
Watch out for
FOR i ← 1 TO 4
Runs once for each value, 1 to 4 included
i never goes past the limit. FOR i ← 10 TO 1 STEP -4 gives 10, 6, 2
WHILE … ENDWHILE
At the start of each pass
If the condition is False to begin with, the body runs zero times
REPEAT … UNTIL
At the end of each pass
The body always runs at least once; it stops when the condition becomes True
for i in range(1, 5):
Python: like FOR
The stop value is left out: 1, 2, 3, 4
With nested loops, the inner loop runs all the way through on each outer pass
Worked exampleTrace this nested loop.
total ← 0
FOR i ← 1 TO 2
FOR j ← 1 TO 3
total ← total + j
ENDFOR
ENDFOR
OUTPUT total
total
i
j
OUTPUT
0
1
1
1
3
2
6
3
7
2
1
9
2
12
3
12
j goes 1, 2, 3 for i = 1, then starts again at 1 for i = 2
Output: 12. The inner body ran 2 × 3 = 6 times.
Exam tipIf an OUTPUT is inside a loop, it appears on every pass: don’t write one output at the end. If it is after the loop, it appears once. Nested-loop traces lose the most marks: keep going until every counter reaches its final value.
3.1.1 Determine the purpose of simple algorithms
Tracing with arrays and indexes
Arrays (lists in Python) are indexed from 0 unless the question says otherwise. nums[i] means “the item at position i”, using whatever i is right now.
LEN(nums) is the number of items, so the last index is LEN(nums) - 1.
A column headed nums[i] helps: write the item you are looking at on each pass.
If an item in the array changes, show the new value (some questions give a column for each position).
An index past the end, such as nums[4] in a 4-item array, causes an error.
Worked exampleTrace this algorithm.
nums ← [6, 2, 9, 4]
count ← 0
FOR i ← 0 TO LEN(nums) - 1
IF nums[i] MOD 2 = 0 THEN
count ← count + 1
ENDIF
ENDFOR
OUTPUT count
count
i
nums[i]
OUTPUT
0
1
0
6
2
1
2
2
9
3
3
4
3
LEN(nums) - 1 = 3, so i runs 0 to 3; count goes up only for even items
Output: 3. Its purpose: it counts the even numbers in the array.
3.1.1 Determine the purpose of simple algorithms
DIV, MOD and string operations
SUBSTRING includes both ends: SUBSTRING(1, 3, s) gives positions 1, 2 and 3. Python’s slice s[1:4] leaves out position 4.
Positions in strings start at 0, like arrays.
In Python, / always gives a decimal: 8 / 4 is 2.0.
Operation
AQA pseudo-code
Python
Result
Whole-number division
17 DIV 5
17 // 5
3
Remainder
17 MOD 5
17 % 5
2
Ordinary division
17 / 5
17 / 5
3.4
Last digit of a number
3725 MOD 10
3725 % 10
5
String operation
AQA pseudo-code
Python
Result
Length
LEN('trace')
len("trace")
5
One character
—
"trace"[1]
r
Substring
SUBSTRING(1, 3, 'trace')
"trace"[1:4]
rac
Position of a character
POSITION('trace', 'c')
"trace".find("c")
3
Join (concatenate)
'tr' + 'ace'
"tr" + "ace"
trace
Character code
CHAR_TO_CODE('a')
ord("a")
97
Exam tipWhere the code uses DIV (or //), the answer is a whole number: 17 DIV 5 is 3, not 3.4. Examiners see students doing ordinary division here every year.
3.1.1 Determine the purpose of simple algorithms
Writing the exact output
When a question asks for the output, write exactly what would appear on the screen.
No quotation marks.print("Hello") outputs Hello.
f-strings: write the text and the values, not the braces. f"{name} scored {score}" outputs Sam scored 7.
print(a, b) puts one space between the items. + joins strings with no space.
Each print() starts a new line.
Integer division gives 3; ordinary division in Python gives 3.0 or 3.4.
Sam scored 14 pointsthe f-string works out score * 2
Total: 7+ joins the strings; the space is inside the quotes
1.0/ gives a decimal in Python
Four lines: Well done Sam / Sam scored 14 points / Total: 7 / 1.0
Exam tipExaminers don’t accept quotation marks around outputs, or f-string braces copied into the answer. Write the output as a person would see it.
3.1.1 Determine the purpose of simple algorithms
Determining the purpose of an algorithm
Questions often end: “State the purpose of the algorithm.” Trace it with an example, or read it and look for a pattern, then say in plain words what it achieves.
If you see…
It probably…
total ← total + x inside a loop
adds up (totals) the values
count ← count + 1 inside an IF inside a loop
counts the items that meet the condition
a value compared with a “best so far” and replacing it
finds the largest or smallest
MOD 2 = 0
checks for even numbers
a temporary variable used to swap neighbouring items, inside nested loops
sorts the array
reversed ← char + reversed
reverses a string
Worked exampleState the purpose of this algorithm.
word ← USERINPUT
result ← ''
FOR char IN word
IF char ≠ ' ' THEN
result ← result + char
ENDIF
ENDFOR
OUTPUT result
Try 'to do list': t, o kept; space skipped; d, o kept; space skipped; l, i, s, t kepta quick trace
Output: todolistevery character except spaces
It removes the spaces from the input (and outputs the result).
Exam tipGive the purpose, not a line-by-line description, and don’t define “algorithm”. A variable called temp usually means temporary, not temperature: a swap needs one.
3.1.1 Determine the purpose of simple algorithms
Tracing subroutine calls and return values
At a call, jump into the subroutine. Its parameters take the values passed in.
Run it until RETURN, then take the returned value back to the exact place where the call was, and carry on there.
A call inside a call: work out the innermost call first.
A procedure (no RETURN) may OUTPUT; a function RETURNs a value, which isn’t output unless the main program outputs it.
Each return value goes back to where its call was made
Worked exampleState the output.
SUBROUTINE square(n)
RETURN n * n
ENDSUBROUTINE
SUBROUTINE addSquares(a, b)
RETURN square(a) + square(b)
ENDSUBROUTINE
result ← addSquares(2, 3) + 1
OUTPUT result
addSquares(2, 3) is called with a = 2, b = 3the main program’s first call
square(2) returns 4; square(3) returns 9the calls inside it
addSquares returns 4 + 9 = 13back to the main program
result ← 13 + 1 = 14carry on where the call was
Output: 14
Exam tipDon’t stop after the first call, and don’t write the call itself (“square(2)”) as an answer: the answer is the value it returns.
Genious