Trace tables and dry-runs

Hello students, welcome to Kwickprep. In the exam hall there is no computer to run your program. So how do you find what an algorithm outputs? Today we will learn dry runs and trace tables, step by step.

First, a new term. A dry run means working through an algorithm by hand, pretending to be the computer. You follow the lines one at a time, in the same order the computer would. Each time a variable changes, you write down its new value. You need only a pen and paper, no computer.

We record a dry run in a trace table. A trace table is a table that shows how values change as an algorithm runs. It has one column for each variable. It usually has one more column for output. You move to a new row as the values change, especially on each pass of a loop.

Trace tables have three main uses. They show the exact output of an algorithm. They help you find logic errors, where the program runs but gives a wrong answer. They also help you work out the purpose of an algorithm you have never seen before.

Here is an algorithm to trace. The arrow means store a value. Total starts at zero. The loop runs three times, and each time it inputs a number and adds it to Total. At the end, it outputs Total. The inputs will be five, eight and two.

Now we fill in the trace table row by row. Before the loop, only Total has a value, zero. On the first pass, Count is one, Num is five, and Total becomes five. On the second pass, Count is two, Num is eight, and Total becomes thirteen. On the third pass, Count is three, Num is two, and Total becomes fifteen. The loop ends, and the output is fifteen.

We can check our dry run with the same algorithm in Python. Instead of typing inputs, the three numbers are stored in a list. The loop adds each number to total. The computer prints fifteen, the same answer as our trace table.

Now a harder one with a while loop. A while loop repeats as long as its condition is True. Double slash is integer division, which divides and throws away any remainder. So twenty double slash two is ten, and five double slash two is two. Let us trace it before we trust the output.

We start with num twenty and count zero. Twenty is more than one, so num becomes ten and count becomes one. Ten is more than one, so num becomes five and count becomes two. Five is more than one, so num becomes two and count becomes three. Two is more than one, so num becomes one and count becomes four. Now one is not more than one, so the loop stops and the output is four.

Pause and predict. What if num starts at one instead of twenty? Is one greater than one? No, it is False. So the loop body never runs, not even once. The program outputs zero, because count was never changed.

The trace table also reveals the purpose of this algorithm. It counts how many times a number can be halved using integer division. It stops when the number reaches one. Twenty can be halved four times, giving ten, five, two and one.

Follow these rules to score full marks. Go through the lines in exactly the order the computer would. Only write a new value in a column when that variable changes. Check the loop condition again at the start or end of every pass. And write any output in the output column, in the row where it happens.

Let us revise what we learned today. A dry run means working through an algorithm by hand. A trace table records values as they change. It has one column for each variable, plus a column for output. It helps you find the output, logic errors and the purpose of an algorithm. And always check the loop condition on every pass.