Trace tables and correcting algorithms

Computer Science · Algorithm design and problem-solving. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Computer Science topics

The idea

A trace table records a dry run: you work through an algorithm by hand, one line at a time, and write down every change. The table has one column for each variable and one for the output. A new value is written only when a variable changes.

Tracing shows what an algorithm really does, so it is also the way to find errors. Most errors in exam algorithms are small: a variable set to its starting value in the wrong place, a wrong comparison such as < where <= is needed, AND mixed up with OR, or a loop that runs one time too many or too few.

Do not guess the result from what the algorithm looks like it should do. Follow the lines exactly.

Rules to remember

A WHILE loop tests its condition before each pass, so it may run zero times. A REPEAT ... UNTIL loop tests at the end, so it always runs at least once.
A REPEAT loop stops when its condition becomes true. A WHILE loop stops when its condition becomes false.
DIV(x, y) gives the whole-number part of x ÷ y. MOD(x, y) gives the remainder. DIV(17, 5) = 3 and MOD(17, 5) = 2.
MOD(Num, 2) = 1 means Num is odd. MOD(Num, 2) = 0 means Num is even.
Totals and counts must be set to 0 before the loop, not inside it.
To accept values from 0 to 100 inclusive, use >= 0 AND <= 100.
When a loop ends on a special value, input before the loop and again at the end of the loop, so the special value is not processed.

Common mistake

Students stop tracing one pass too early or too late. Test the loop condition with the new values every time, and remember that the variable may change once more after the value you expected.

Worked example

What is output by this algorithm?
N ← 13
Count ← 0
WHILE N > 1 DO
N ← DIV(N, 2)
Count ← Count + 1
ENDWHILE
OUTPUT Count

Start: N = 13, Count = 0. 13 > 1 is true, so N = DIV(13, 2) = 6 and Count = 1.
6 > 1 is true, so N = DIV(6, 2) = 3 and Count = 2.
3 > 1 is true, so N = DIV(3, 2) = 1 and Count = 3.
1 > 1 is false, so the loop stops.

Answer: The output is 3.

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Keep going

← Validation, verification and test data Variables, data types and operators →Take a Computer Science test