Analysing Algorithms

1. What a Trace Table Is

One of the ways to identify an algorithm’s purpose is to dry run a program on paper using a Trace Table. This is a table containing all the variables in use in the program.

The purpose of a Trace Table is to see what our variables are doing at each stage in a program. This allows us to detect where things are not happening as expected.

Let’s look at some simple pseudocode:

firstNumber ← 5
secondNumber ← 5
result ← firstNumber + secondNumber
OUTPUT result

To put together a trace table we need to identify how many variables we have. Each variable will correspond to a column.

We have three variables: firstNumber, secondNumber and result. This means we’ll need three columns, one for each variable. We’ll also need an output column.

Have any variables been initialised at the start of our program? Yes, firstNumber and secondNumber are both set to 5.

Next, our program will perform the calculation and store the result in the variable result. This is then output to the user.

This trace table will not allow us to correct any errors, but we can see very clearly the purpose of the algorithm is to add two numbers.

2. Trace Tables with Loops

In programming, loops are a piece of code that lets us run a block of code many times over. Trace tables are a very useful tool for tracking how our data changes each time a loop is completed.

Let’s look at the simple loop pseudocode below:

num ← 0
total ← 0
FOR i ← 0 TO 4
   num ← i * 2
   total ← num + total
ENDFOR
OUTPUT total

As before we will first want to create our table with columns for each of our variables and our output.

We have three variables: num, total and i. This means we’ll need three columns, one for each variable. We’ll also need an output column.

We’ve also initialised both num and total to 0.

Now we enter our loop. In our loop we have create a variable called i which will start at 0 and increment each loop until we reach 4. So during the first loop i is 0.

During the loop we multiply i by 2 and store this in the num variable. We then add num to our total variable and store this back in total. Due to i being 0, and 0 * 2 returning 0, num and total don’t actually change.

We can see this completed below.

We have now completed one pass of our loop. Our code will now automatically increment i and go back to the top of our loop code (line 3).

It will then perform the code block within the loop again.

This code will repeat now until the end of the loop where i = 4. We then print our output (the contents of our total variable).

We can see the completed trace table below.

3. Correcting & Completing Algorithms with Trace Tables

Trace tables are a great tool for identifying and correcting errors within an algorithm.

Let’s say we have an algorithm that we think will print out the first 5 numbers in your 7 times table.

counter ← 1
result ← 0
WHILE counter < 6
   result ← counter * 7
   OUTPUT result
ENDWHILE

We have two variables: counter, and result. This means we’ll need two columns, as well as an output column.

We’ve also initialised both counter to 1 and result to 0.

Now we enter our loop and start recording what happens to each of our variables as they pass through it.

In our loop we multiply the counter variable by 7 and store the result in the variable “result”. We then print out the result.

After completing the first loop our trace table looks like this:

Let’s now continue to build our trace table.

Can you see the mistake?

At no point are we actually adding 1 to counter, so the code “while counter < 6” is never reached. This is an example of an infinite loop.

Let’s try and correct the code by incrementing counter at the end of each loop.

counter ← 1
result ← 0
WHILE counter < 6
   result ← counter * 7
   OUTPUT result
   counter ← counter + 1
ENDWHILE

Let’s dry run this code and complete our trace table.

Our code works!