Trace tables: dry-running an algorithm

Last time

Before we start: last time, in Test data, you learned these points. Here they are again on one card. Keep them in mind, because today builds on them.

Be the computer

You can find out what an algorithm does without ever running it on a machine. You pretend to be the computer. You follow each instruction, one at a time, and write down every value. The table you fill in is called a trace table, and the exercise is a dry run.

What is a trace table?

A trace table records the value of every variable, and every output, as an algorithm runs. It is a step-by-step dry run, done on paper. It is used to see how an algorithm works, and to find logic errors.

The rules

Make one column for each variable, and one for the output. Write a new row each time a value changes. Fill in only the cells that change; leave the others blank. Put the output exactly as the algorithm prints it. Take the test data in the order it is given, one value per INPUT.

The first algorithm

Here is an algorithm. Total and Count start at zero. It keeps reading numbers until zero is entered. If a number is over ten, it is added to Total, and Count goes up by one. At the end, it outputs both.

Dry run: 12, 5, 20, 0

The test data is twelve, five, twenty, zero. Total and Count are set to zero. Twelve is over ten: Total twelve, Count one. Five is not over ten, so nothing changes. Twenty is over ten: Total thirty-two, Count two. Zero ends the loop, and the output is thirty-two, two.