Lesson video

Hello, my name is Mrs. Holbrook, and welcome to Computing.

I'm so pleased that you've been able to join me for today's lesson.

Today we are going to be looking at how trace tables can be used to check the logic of an algorithm.

Trace tables are a great tool for testing, so let's see how they work.

Welcome to today's lesson from the unit algorithms. This lesson is called tracing algorithms, and by the end of today's lesson, you'll be able to use trace tables to test the logic of an algorithm.

Shall we make a start? We will be exploring these keywords throughout today's lesson.

Trace table.

Trace table, a tool used to track the values of variables and the flow of execution in an algorithm or programme, step by step.

Error.

Error, a mistake or unexpected behaviour in a programme that prevents it from working correctly.

Modulo.

Modulo, an operation that gives the remainder when one number is divided by another.

Today's lesson is broken down into two parts.

We'll start by understanding trace tables and then we'll move on to use trace tables to test the logic of an algorithm.

Let's make a start by understanding trace tables.

Look at the flow chart below.

We have a start.

We are then setting two variables, count to one and total to zero.

We then have a decision which says is count less than five.

If it is, then total is going to be equal to total plus count, and we are going to increment the counter by one.

If not, if it's false, then we are going to output the total and we are going to end.

What is the output when this flow chart is executed? Is it A, four, B, 10, C, 15, or D, there's an error in the flow chart.

Maybe pause the video and have a think.

Did you select B 10? Well done.

Let's have a look why that's the case.

So at the top we are setting the two variables, count to one and total to zero.

So we're assigning one to the variable count and we're assigning zero to the variable total.

We then move on to our decision, to check if the condition is true.

So is count less than five? Count is less than five.

So we are going to add the value of count to the value held by total.

So total is now become one.

We then are going to add one to the value held by count.

So count now holds the value two, and we go back round.

Check if the condition is true, count is still less than five.

So we are going to add the value of count to the value held by total.

So total now becomes three and we are going to increment count by one.

So count is now equal to three.

We go back round.

Count is still less than five, so the condition is still true.

We're going to add the value of count to the value held by total.

So total becomes six, and we're going to increment count by one.

So count now becomes four.

Background count is still less than five, so the condition is still true.

We are going to add total to count, so total is gonna become 10.

Then we're gonna increment count.

So count is now equal to five, so is count now less than five.

The condition is false, so we are gonna output the value of total, which is 10.

Walking through an algorithm like we've just done and checking the state of variables is a useful tool for understanding how the algorithm works.

Walking through an algorithm can help detect and correct errors.

A trace table can be used to help walk through the steps of an algorithm.

A trace table is like a notebook for tracking how an algorithm or programme works.

A trace table allows you to formally record the state of variables, the outputs, and the condition evaluations, as you mentally execute the algorithm.

A trace table could have been used to record the state of variables, the outputs, and the condition of valuations during the walkthrough in the previous flow chart example.

So here you can see we've got the variables count and total, and then we've got the value of the condition whether it returns true or false.

There are several advantages of using trace tables such as, providing a clear step-by-step visual representation of how an algorithm processes data, helping to pinpoint errors in logic or calculations before they become larger problems in the code.

Offering a structured way to grasp how algorithms work and how variables change over time.

There are many ways to create trace tables.

The exact format, layout and structure will vary for each algorithm.

Note that although trace tables are useful to spot errors, they can still be subject to human error, especially when tracing complex algorithms. A trace table will contain vertical columns that may represent important information such as the line variables, conditions, and outputs of the algorithm.

The number of columns needed as well as the columns names will vary with each algorithm.

A trace table will contain horizontal rows that represent each step in the execution of an algorithm.

The number of rows needed in the trace table will vary with each algorithm.

Time to check your understanding.

In a trace table what does each row typically represent? Is it A, a variable in the algorithm.

B, a condition in the algorithm.

or C, a step in the algorithm.

Pause the video whilst you have a think.

That's correct.

A row will typically represent a step in the algorithm.

True or false? Trace tables are helpful for finding logic errors in algorithms. Pause the video whilst you have a think.

That's right, it's true.

Okay, we are moving on to our first task of today's lesson.

Write a paragraph to explain what a trace table is and why they may be used? Pause the video whilst you complete the activity.

How did you get on? You're doing a great job so far, so well done.

A trace table is used to record and track the execution steps of an algorithm.

A trace table has columns that represent important information such as the line, variables, conditions and outputs.

The rows in the table represent each line of the algorithm.

The values of the variables in the table are written down with each step so you can see how they change over time.

Trace tables are used because they can help pinpoint errors in logic or calculations before they become larger problems. They also provide a clear step-by-step visual representation of how an algorithm processes data.

Remember, if you need to pause the video here, and add any additional notes to your answer, you can do that now.

Okay, we are now moving on to the final part of today's lesson, where we're going to use trace tables to test the logic of an algorithm.

Look at the code below.

Lucas asks, "What do you think the code does?" Maybe pause the video whilst you have a quick think.

Lucas has written the code in Python.

Lucas says, "The programme should output all the numbers between zero and the input value that are divisible by three." Sam's got a really good question.

"What does the percent operator do? I don't understand that part of the code." Lucas says, "The percent symbol means modulo.

It gives you the remainder when one number is divided by another." Sam says, "Oh, I think I understand now.

So this part of the code checks if the remainder of the num variable divided by three is zero?" Lucas says, "Yes, that's right." Lucas says, "I think it would be great to use a trace table to step through my code and test the code executes without any logical errors." Sam says, "I think that's a great idea, Lucas." Let's go and do that now.

In this example, a trace table will be used to test the logic of Lucas's algorithm that is implemented in Python.

Note that trace tables can also be used to test the logic of algorithms represented in other forms such as flow charts, pseudocode and code in other programming languages.

First, we have to identify the variables and add them to the headings.

So we have num, which is a variable, which is an integer.

The first line has no variables, conditions or outputs, so nothing is added.

The second line, the user inputs a value.

For this example, the value six is assigned to the num variable and this is recorded in the trace table.

So we've got line two number is equal to six.

Line three has a condition which is num greater than two.

The condition is of evaluated and the value recorded in the table.

So in this case it's true.

Line four has a condition num percent three is equal equal to zero.

It uses modulo to calculate the remainder of the num divided by three.

In this case six mod three calculates to zero, so the condition evaluates to true there is no remainder.

As the condition for line four was true, we step into the IF statement.

Line five produces an output, so it's recorded in the table, and six is output.

Line six has a variable assignment.

The expression num minus one retrieves the current value of num and reduces it by one.

This new value replaces the value of num, so num is now equal to five and we've recorded that in the trace table.

We then go back round the while loop.

So num is still greater than two.

So the condition on line three is true and is recorded.

Again, line four uses modulo to calculate the remainder of num divided by three.

This time, five mod three calculates as two.

So the condition of evaluates as false.

Note, we skip line five this time round because the condition was false.

Line six has the variable assignment, so we record this.

So num minus one is four.

We then go back to the while loop because the condition on line three is true and we record this in the truth table.

What will the condition on line four evaluate to? Maybe pause the video whilst you have a think.

That's right, it'll evaluate to false.

In this case, four mod three calculates as one.

So again, the condition evaluates to false.

We skip line five and go to line six and we take the value of one away from number.

So number is now three, go to line three.

The condition is still true.

The if statement, so three mod three will calculate a zero, so there's no remainder, so that evaluates as true.

This time we do run line five, so we're going to print out that number.

So three and we record that in the trace table and then we take one away from number.

So num is now equal to two, and then this time our condition on line three is no longer true, it's false and the programme will now end.

The trace table has helped to show that the programme does only output numbers divisible by three based on the given input.

If there had been a logic error, it would've been easy to spot exactly where the problem had been when executing the code.

True or false? Trace tables can only be used with pseudocode, not with actual code.

Pause the video whilst you have a think.

That's right, it's false.

Trace tables can be used to test the logic of algorithms represented in other forms such as flowchart, pseudocode, and other programming languages.

In Python, integer division can be used to calculate the whole number of times a divisor will go into a dividend.

For example, 7 // 3 will calculate as two.

So seven is the dividend and three is the divisor.

Note that integer division is also used in many other programming languages.

Time to check your understanding.

Aisha is performing an integer division calculation in Python.

State the result of 15 // 4.

Is it A three, B four or C five? Pause the video whilst you have a think.

That's right.

The correct answer is A, three.

This is because four will go into 15 three whole times.

Okay, we are now moving on to our final task of today's lesson.

Look at the code below.

The code is an implementation of the Russian multiplication algorithm.

This method calculates the product of two numbers as a sum by using integer division and modulo.

One, state the result of the following calculations in Python? A, 14 % 4 and B, 28 // 5.

Pause the video whilst you answer the question.

How did you get on? So for part one, four goes into 14, three whole times and the remainder is two.

So the result would be two because remember this is modulo division, so it returns the remainder.

And then for B, five is the divisor and 28 is the dividend.

So the result will be five.

For part two complete the trace table using the algorithm, the values of A and B and the first iteration of the while loop have been filled in for you already.

Pause the video whilst you complete the trace table.

How did you get on? Did you manage to complete the trace table? Great work.

Note that this answer continues from the starter answers already given in the trace table.

So you can see that we've started the trace table on line six.

So six, the condition returns true, line seven sum is equal to 33.

Line eight A, is equal to 44, and then on line nine B is equal to one.

The condition on line five returns true as does the condition on line six.

On line seven, sum is set to 77, and on line eight A, is set to 88.

On line nine B, is set to zero.

We revisit the condition on line five, which then is false, which means that we skip to line 10 and the number 77 is output.

If your truth table doesn't quite look like this, maybe pause the video, go back a few slides and have another go.

Okay, we've come to the end of today's lesson and you've done a fantastic job, so well done.

Let's summarise what we've learned together.

Trace tables can be used to walk through and understand the logic of an algorithm.

Trace tables can be used to test the logic of algorithms represented in many forms such as flow charts, pseudocode, and other programming languages.

Trace tables can be used to help find logical errors in algorithms. I hope you've enjoyed today's lesson.

You've done a fantastic job, so well done.

See you again soon.

Bye.