IGCSE CS: 7.7 Trace Tables and Dry Runs

Objectives: Students should be able to —

1 Define what is meant by a trace table and a dry run of an algorithm.
2 State the purpose of using trace tables when testing an algorithm.
3 Identify the variables, inputs and outputs that should appear as columns in a trace table.
4 Use the pre-defined functions DIV and MOD in pseudocode and trace their values.
5 Complete a trace table for a given pseudocode algorithm and a given set of input data.
6 Use a completed trace table to determine the output and describe the purpose of an algorithm.
7 Use a trace table to identify and locate logic errors in an algorithm.

Trace Tables and Dry Runs — Definitions and Purpose

(a) Trace table:

A trace table is a table that contains columns for each variable and a column for any output.

It is a tabular method used to trace and record the value of variables as each line of code is dry-run for a given set of input data.

(b) Dry run:

A dry run means that you do not actually run the code in a computer — instead, you work through it on paper, line by line, recording how the values of each variable change.

It is the manual process of executing an algorithm step-by-step to predict what the computer would do if the program were to be executed.

To determine what a computer would do if the program were to execute.
To test the logic of an algorithm, and find errors (if any) that are not easily spotted just by reading the code.

To check that the logic of the algorithm is correct before any code is written — fixing a logic error on paper is far quicker than debugging a finished program.
To predict the expected output for a known set of inputs. Once the program is run, the actual output can be compared with the predicted output to confirm the program works.
To identify logic errors that are not easily spotted by reading the code — for example, an off-by-one error in a loop, or a comparison that uses > instead of >=.
To confirm that all variables have been initialised before they are used, and that they take the values the programmer expects at each step.

Note: A dry run does not require a compiler, interpreter or computer — only paper and a pencil. This makes it the fastest way to test algorithm logic during the design stage.

Pre-Defined Functions DIV and MOD

(a) DIV:

The pre-defined function DIV gives the value of the result of integer division — that is, the whole-number quotient when one integer is divided by another, with the remainder discarded.

Example: Y = 9 DIV 4 gives the value Y = 2 (because 9 ÷ 4 = 2 remainder 1; the quotient is 2).

(b) MOD:

The pre-defined function MOD gives the value of the remainder of integer division — that is, the amount left over after one integer is divided by another.

Example: R = 9 MOD 4 gives the value R = 1 (because 9 ÷ 4 = 2 remainder 1; the remainder is 1).

Expression	Working	Value
17 DIV 5	17 ÷ 5 = 3 r 2 → quotient	3
17 MOD 5	17 ÷ 5 = 3 r 2 → remainder	2
100 DIV 7	100 ÷ 7 = 14 r 2 → quotient	14
100 MOD 7	100 ÷ 7 = 14 r 2 → remainder	2

Note: For any two integers A and B, the relationship A = (A DIV B) × B + (A MOD B) always holds. This is the basis of many trace-table checks.

Identifying Columns of a Trace Table

Total ← 0 Count ← 0 INPUT Num WHILE Num <> 0 Total ← Total + Num Count ← Count + 1 INPUT Num ENDWHILE Average ← Total / Count OUTPUT Total, Average

Method: Walk through the pseudocode and write down every variable that is assigned a value, every variable that is INPUT, and every value that is OUTPUT. Each of these needs its own column in the trace table.

Column	Why it appears	Type
Num	Read in by INPUT, also used in the WHILE condition and to update Total	Variable (input)
Total	Initialised to 0, then accumulates the running sum inside the loop	Variable (accumulator)
Count	Initialised to 0, then increments by 1 inside the loop	Variable (counter)
Average	Computed after the loop ends: Total / Count	Variable (computed)
Output	Produced by the OUTPUT statement at the end of the algorithm	Output column

So the trace table should have the column headings: Num · Total · Count · Average · Output.

Note: A constant (such as a fixed value used in the algorithm) does not need its own column — only variables whose values change and any output produced should be recorded.

Completing Trace Tables — Algorithms with Selection

First ← 0 Last ← 0 INPUT Limit FOR Counter ← 1 TO Limit INPUT Value IF Value >= 100 THEN IF Value < 1000 THEN First ← Value DIV 100 Last ← Value MOD 10 IF First = Last THEN OUTPUT Value ENDIF ENDIF ENDIF NEXT Counter

(a) Completed trace table:

Counter	Value	First	Last	Limit	Output
—	—	0	0	8	—
1	66	0	0	8	—
2	606	6	6	8	606
3	6226	6	6	8	—
4	8448	6	6	8	—
5	642	6	2	8	—
6	747	7	7	8	747
7	77	7	7	8	—
8	121	1	1	8	121
—	—	1	1	8	—

Reasoning for each row:

Counter = 1, Value = 66: 66 < 100 → outer IF is FALSE → First and Last stay at 0; no output.
Counter = 2, Value = 606: 606 ≥ 100 AND 606 < 1000 → three-digit. First = 606 DIV 100 = 6, Last = 606 MOD 10 = 6. First = Last → OUTPUT 606.
Counter = 3, Value = 6226: 6226 >= 100 but 6226 > 1000 → inner IF FALSE → no change to First / Last, no output.
Counter = 4, Value = 8448: same as 6226 → no change, no output.
Counter = 5, Value = 642: three-digit. First = 642 DIV 100 = 6, Last = 642 MOD 10 = 2. 6 ≠ 2 → no output.
Counter = 6, Value = 747: three-digit. First = 747 DIV 100 = 7, Last = 747 MOD 10 = 7. First = Last → OUTPUT 747.
Counter = 7, Value = 77: 77 < 100 → outer IF FALSE → no change, no output.
Counter = 8, Value = 121: three-digit. First = 121 DIV 100 = 1, Last = 121 MOD 10 = 1. First = Last → OUTPUT 121.

(b) Purpose of the algorithm:

The algorithm checks and accepts only three-digit numbers (numbers in the range 100 to 999). It rejects any number that has fewer than three digits (e.g. 66, 77) or more than three digits (e.g. 6226, 8448).

For each accepted three-digit number, it calculates the first digit (using DIV 100) and the last digit (using MOD 10), then outputs the number only if the first and last digits are the same.

In short: The algorithm finds and outputs all the three-digit palindrome-style numbers from the input list — that is, three-digit numbers whose first and last digits are equal (such as 606, 747 and 121).

Highest ← 0 FOR Count ← 1 TO 5 INPUT Number IF Number > Highest THEN Highest ← Number ENDIF NEXT Count OUTPUT Highest

Method: Trace one iteration of the FOR loop per row. Read in a Number, compare it to Highest, and update Highest only if Number is greater.

Count	Number	Highest	Output
—	—	0	—
1	45	45	—
2	62	62	—
3	18	62	—
4	79	79	—
5	30	79	79

Output: 79 — the algorithm reads five numbers and outputs the highest.

Trace Tables for Loops and Error Detection

INPUT N Product ← 1 Counter ← 1 WHILE Counter <= N Product ← Product * Counter Counter ← Counter + 1 ENDWHILE OUTPUT Product

Method: Evaluate the WHILE condition before each iteration. Update Product (multiply by Counter), then increment Counter. Stop when Counter > N.

N	Product	Counter	Counter <= N?	Output
5	1	1	TRUE	—
5	1	2	TRUE	—
5	2	3	TRUE	—
5	6	4	TRUE	—
5	24	5	TRUE	—
5	120	6	FALSE	120

Output: 120

The algorithm calculates the factorial of N — that is, 5! = 1 × 2 × 3 × 4 × 5 = 120.

Sum ← 0 FOR Num ← 1 TO 10 IF Num MOD 2 = 1 THEN Sum ← Sum + Num ENDIF Num ← Num + 1 NEXT Num OUTPUT Sum

(a) Trace table:

Num (loop)	Num MOD 2 = 1?	Num after +1	Sum	Output
1	TRUE	2	1	—
3	TRUE	4	4	—
5	TRUE	6	9	—
7	TRUE	8	16	—
9	TRUE	10	25	—
11	FALSE (11 > 10, loop exits)	—	25	25

Analysis: Tracing the table shows the algorithm produces 25, not 30. So the reported result of 30 cannot come from this pseudocode alone. Re-examining the algorithm reveals the bug: the line Num ← Num + 1 is placed inside the FOR loop body, but the FOR loop itself already increments Num at NEXT Num. The variable Num is therefore being incremented twice per pass, which is why the trace skips even numbers (1 → 3 → 5 → 7 → 9). In a different implementation of the FOR statement (where the increment happens at the bottom), this extra Num ← Num + 1 would cause the loop to take values 1, 3, 5, 7, 9, 11 — but with the value 9 included the running sum is 25.

Conclusion: The bug is the redundant line Num ← Num + 1. It is also a logic error (not a syntax error), because the program runs but does not behave as the programmer intended.

(b) Correction:

Remove the redundant line Num ← Num + 1 from inside the loop body. The FOR Num ← 1 TO 10 ... NEXT Num construct already increments Num by 1 at each pass, so the manual increment is unnecessary and incorrect.

Sum ← 0 FOR Num ← 1 TO 10 IF Num MOD 2 = 1 THEN Sum ← Sum + Num ENDIF NEXT Num OUTPUT Sum

After the fix, the loop runs through Num = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 and the IF selects only the odd values. The final output is 25, as expected.

INPUT Number Count ← 0 REPEAT Number ← Number DIV 2 Count ← Count + 1 UNTIL Number = 0 OUTPUT Count

Method: The REPEAT…UNTIL loop runs the body at least once, then checks the condition. Integer-divide Number by 2 each pass and increment Count, until Number becomes 0.

Pass	Number (before)	Number ← Number DIV 2	Count	Number = 0?
1	25	12	1	FALSE
2	12	6	2	FALSE
3	6	3	3	FALSE
4	3	1	4	FALSE
5	1	0	5	TRUE → OUTPUT 5

Output: 5

Note: The algorithm counts how many times the input number can be integer-divided by 2 before it becomes 0. For 25 this is 5 passes (25 → 12 → 6 → 3 → 1 → 0). The trace makes this behaviour visible — without it, the answer 5 would be hard to predict just by reading the code.

DECLARE List : ARRAY[1:5] OF INTEGER FOR I ← 1 TO 5 INPUT List[I] NEXT I Smallest ← List[1] FOR I ← 2 TO 5 IF List[I] < Smallest THEN Smallest ← List[I] ENDIF NEXT I OUTPUT Smallest

(a) Trace table:

I	List[1]	List[2]	List[3]	List[4]	List[5]	Smallest	Output
1	12	—	—	—	—	—	—
2	12	7	—	—	—	—	—
3	12	7	18	—	—	—	—
4	12	7	18	4	—	—	—
5	12	7	18	4	9	—	—
After first loop: Smallest ← List[1] = 12						12	—
2	12	7	18	4	9	7	—
3	12	7	18	4	9	7	—
4	12	7	18	4	9	4	—
5	12	7	18	4	9	4	4

(b) Value output:

The algorithm outputs 4.

The algorithm reads five integer values into an array, then finds and outputs the smallest value in the array.

Method: Initialise Smallest to the first element of the array, then iterate through the remaining elements. Each element is compared to Smallest; if it is smaller, Smallest is updated. After the loop, Smallest holds the minimum value.

Revision: Statements and Key Computing Terms

Statement	Key Term
A table containing columns for each variable and a column for any output, used to record values as an algorithm is dry-run.	Trace table
Working through an algorithm on paper, line by line, without running it on a computer.	Dry run
A named storage location whose value can change during the execution of an algorithm.	Variable
A named value that is set once and does not change during the execution of an algorithm.	Constant
Pre-defined function that gives the integer quotient when one number is divided by another.	DIV
Pre-defined function that gives the remainder when one number is divided by another.	MOD
A variable that keeps a running total by adding values to it inside a loop.	Accumulator (Totalling)
A variable that is incremented by 1 each pass through a loop, used to record the number of iterations.	Counter
A programming construct that allows a block of code to be executed repeatedly while or until a condition is met.	Iteration (Loop)
A programming construct in which a block of code is executed only if a condition is TRUE (e.g. IF…THEN…ENDIF).	Selection
An error in an algorithm that produces an unexpected result, but does not stop the program from running.	Logic error
An error that breaks the rules of the programming language and stops the program from running at all.	Syntax error
A function built into a programming language that performs a common task (e.g. DIV, MOD, LENGTH, ROUND).	Pre-defined function
The data produced by an algorithm and sent to the user (e.g. via OUTPUT statement).	Output