Analysing Algorithms

Whether you are using flowcharts or pseudocode, you may be given an algorithm to review or to look at to evaluate.

For simple algorithms, it can often be possible to identify their purpose and fix any issues through visual inspection of the code.

However, in more complex situations, a tool called a trace table can be useful.

In this lesson, we’ll learn about:

1. What a trace table is
2. Using trace tables with loops
3. Correcting & completing algorithms with trace tables

One way to identify an algorithm’s purpose is to dry-run a program on paper using a trace table. This table contains all the variables used 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 the number of variables. Each variable corresponds 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. It will then output this to the user.

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

In programming, loops are pieces of code that let us run a block of code many times over.

Trace tables are very useful tools 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 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.

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 to 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!

You can also use a trace table to dry-run an algorithm.

This will show how the variables are changing.

Trace tables will show all the variables in an algorithm as well as any outputs.

Trace tables can be used to identify the purpose of an algorithm.

A trace table can be used to correct an algorithm – to spot when something is going wrong.

This is usually done before you start writing some code.