fbpx

Analysing Algorithms

As you are designing your algorithm, you will just have an idea of how it’s going to work on paper. You may be designing using Pseudocode or you may be using flowcharts. Whichever tool you are using, you may be given an algorithm to review or to look at to evaluate.

When this happens it is useful to be able to work out what an algorithm is doing, fix any errors, or recommend solutions to improve the algorithm.

For simple algorithms it can often be possible to identify the purpose of an algorithm and fix any issues through visual inspection of the code. However, in more complex situations it can be useful to use a tool called a Trace Table.

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
Media Attachments: Presentation Video

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.

firstNumbersecondNumberresultoutput

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

firstNumbersecondNumberresultoutput
55

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

firstNumbersecondNumberresultoutput
551010

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.

Further Thought

Can you use a trace table with a flow chart? Try it out.

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.

numtotalioutput
00

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.

numtotalioutput
00
000

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.

numtotalioutput
00
000
221

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.

numtotalioutput
00
000
221
462
6123
820420

Further Thought

There are different types of loop you can use in programming. Research about these online.

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.

counterresultoutput
10

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:

counterresultoutput
10
177

Let’s now continue to build our trace table.

counterresultoutput
10
177
177
177
177
177
177

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.

counterresultoutput
10
277
31414
42121
52828
63535

Our code works!

Further Thought

What would happen if the while loop said “while counter <= 6"?

Lesson Summary

So to summarise what we’ve learnt in this lesson:

  • 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.
Please accept statistics, marketing cookies to view this content.
Scroll to Top
Send this to a friend