Algorithm tracing

CIE A-Level Computer Science· 40 min read

1. Tracing Iterative Algorithms★★☆☆☆⏱ 15 min

📘 Definition

Algorithm Tracing (Dry Run)

The process of manually simulating an algorithm's execution step-by-step, recording the value of every variable and any output produced at each stage.

📐 Worked Example

Trace the pseudocode below that calculates the sum of the first 4 positive even numbers, and find the final output:

sum ← 0
FOR count ← 1 TO 4
    number ← 2 × count
    sum ← sum + number
NEXT count
OUTPUT sum

1
1. Before entering the loop, initialize the declared variable:
2
sum = 0, count and number are unassigned
3
1. First loop iteration: count is set to 1
4
number = $2 \times 1 = 2$ , sum = $0 + 2 = 2$
5
1. Second loop iteration: count increments to 2
6
number = $2 \times 2 = 4$ , sum = $2 + 4 = 6$
7
1. Third loop iteration: count increments to 3
8
number = $2 \times 3 = 6$ , sum = $6 + 6 = 12$
9
1. Fourth loop iteration: count increments to 4
10
number = $2 \times 4 = 8$ , sum = $12 + 8 = 20$
11
1. Loop exits after count increments past 4, final output is:
12
$20$

Exam tip:

Always start your trace table with initial variable values before any loops or conditional blocks run. One mark is almost always awarded for correct initialization.

2. Tracing Nested Control Structures★★★☆☆⏱ 20 min

Nested control structures (if statements inside loops, loops inside loops) require extra care to track which level of execution you are at, and which variables are currently being updated.

📘 Definition

Nested Iteration

A loop that contains another loop (inner loop) inside its body. Each iteration of the outer loop runs the entire inner loop from start to finish.

📐 Worked Example

Trace the following nested pseudocode and write all output produced:

FOR outer ← 2 TO 2
    OUTPUT "2 x: "
    FOR inner ← 1 TO 3
        product ← outer × inner
        OUTPUT product
    NEXT inner
NEXT outer

1
1. Outer loop starts: outer = 2, output the string 2 x:
2
1. First inner loop iteration: inner = 1
3
product = $2 \times 1 = 2$ , output 2
4
1. Second inner loop iteration: inner = 2
5
product = $2 \times 2 = 4$ , output 4
6
1. Third inner loop iteration: inner = 3
7
product = $2 \times 3 = 6$ , output 6
8
1. Inner loop exits, outer loop exits. Full output is:
9
2 x: 2 4 6

Exam tip:

When tracing nested loops, add separate columns for the outer and inner index values to avoid getting lost between iterations.

3. Tracing Recursive Algorithms★★★★☆⏱ 25 min

Recursive algorithms (functions that call themselves with smaller inputs) require tracing each call stack frame separately, to track return values and correctly identify the base case.

📘 Definition

Call Stack Frame

A separate entry on the call stack for each active recursive call, storing the input parameters and return address for that call.

📐 Worked Example

Trace the factorial function $f a c t (n)$ defined below, for input $n = 3$ , find the final return value:

FUNCTION fact(n)
    IF n == 0 THEN
        RETURN 1
    ELSE
        RETURN n * fact(n - 1)
    ENDIF
ENDFUNCTION

1
1. Initial call: $f a c t (3)$ , $n = 3 \neq = 0$ so need to compute $3 \times f a c t (2)$
2
1. New call: $f a c t (2)$ , $n = 2 \neq = 0$ so need to compute $2 \times f a c t (1)$
3
1. New call: $f a c t (1)$ , $n = 1 \neq = 0$ so need to compute $1 \times f a c t (0)$
4
1. New call: $f a c t (0)$ , hit base case, return 1
5
1. Unwind stack: $f a c t (1)$ returns $1 \times 1 = 1$
6
1. Unwind stack: $f a c t (2)$ returns $2 \times 1 = 2$
7
1. Unwind stack: $f a c t (3)$ returns $3 \times 2 = 6$
8
Final return value is:
9
$6$

Exam tip:

Always draw the call stack clearly, labeling each call with its input parameter value. Examiners need to see you understand the order of execution and unwinding.

4. Common Pitfalls

Wrong move:

Only writing the final value of each variable, not updating after every step

Why:

Examiners award 70-80% of marks for intermediate steps, so you lose most marks even if the final output is correct

Correct move:

Update every variable in your trace table every time its value changes, no matter how trivial the change seems

Wrong move:

Off-by-one errors in FOR loops, stopping one iteration too early

Why:

CIE pseudocode FOR loops are inclusive of both start and end bounds, so you must run when the counter equals the end value

Correct move:

Calculate number of iterations as (end - start + 1) to confirm you have the correct number of steps

Wrong move:

Forgetting to reset the inner loop counter for each outer loop iteration in nested loops

Why:

This leads to incorrect inner loop execution and wrong variable values for all subsequent steps

Correct move:

Add separate columns for outer and inner counters, and explicitly reset the inner counter each outer iteration

Wrong move:

Calculating the final return value before reaching the base case for recursion

Why:

Recursive calls depend on the return value of deeper calls, so calculating early leads to wrong results

Correct move:

Draw all calls from initial input down to the base case first, then unwind back upwards to calculate return values

5. Quick Reference Cheatsheet

Algorithm Type	Key Action	Exam Mark Tip
Iterative	Initialize variables first, update every step	1 mark for correct initialization
Nested Loop	Separate columns for outer/inner counters	Iterations = end - start + 1
Recursive	Draw stack down to base case, unwind up	Marks for each correct call frame
Any Tracing	Record all output, not just final result	Missing output = lost marks

6. Frequently Asked

Do I need to show every step in tracing questions?

Yes, CIE examiners award most marks for intermediate steps, not just the final output. Even if your final answer is wrong, you can get partial credit for correct intermediate variable values.

Can I use my own notation for tracing?

As long as your steps are clear and every variable update is recorded, yes, but the standard table format recommended in marking schemes is the safest option to avoid misinterpretation.

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2022 · 2
Trace iterative sort algorithm
2023 · 2
Trace recursive factorial function
2024 · 2
Trace nested loop pseudocode

Going deeper

syllabusCIE 9618 Official SyllabusSee section 9 for learning outcomes

What's Next

Algorithm tracing is a foundational skill for all algorithm problems in CIE 9618, from sorting and searching to recursive problem solving. Mastering step-by-step tracing not only helps you correctly answer dedicated tracing questions, but also lets you debug your own pseudocode when writing original algorithms for open-ended problem solving questions, which carry the majority of marks on Paper 2. Consistent tracing practice builds speed and helps you avoid common errors that cost easy marks in the exam.