ScholaFly

CS10-07 Computer Science Watch

Trace tables

Watch on YouTube

In this lesson

Trace tables: how to use a trace table to follow an algorithm line by line, with worked examples and the mistakes examiners report. Edexcel 1CP2 and OCR J277 GCSE. Algorithms 7 of 9. More at https://scholafly.com

By the end: Use a trace table to follow an algorithm line by line, recording each change to each variable and every output exactly where it happens, and use it to state what a variable holds at a given point and what the algorithm outputs.

What it covers

  1. 0:00 Intro: trace tables
  2. 0:37 Trace tables
  3. 2:56 A counted loop
  4. 4:24 Output inside the loop
  5. 6:44 A loop you have to trace

Key words

About this video

Trace tables | GCSE Computer Science | CS10-07

Trace tables: how to use a trace table to follow an algorithm line by line, with worked examples and the mistakes examiners report.
Edexcel 1CP2 and OCR J277 GCSE. Algorithms 7 of 9.
More at https://scholafly.com

Watch first: CS10-05 - https://youtu.be/Ioa4-no7NkE
Video code: CS10-07 (search "ScholaFly CS10-07")

#GCSEComputerScience #Algorithms #TraceTables

For teachers
This GCSE Computer Science lesson teaches trace tables. By the end, students should be able to use a trace table to follow an algorithm line by line, recording each change to each variable and every output exactly where it happens, and use it to state what a variable holds at a given point and what the algorithm outputs. It works through four worked examples and the mistakes examiners report.

Exam board specification references:
Edexcel 1CP2
- 1.2.4
OCR J277
- 2.1.2

Read the transcript

A bank statement's final balance is wrong. How do you find the exact payment that caused it? Adding everything up again is tempting, but that only proves something is wrong. The balance after each change points to the exact line. A computer does not show its working, so a trace table writes out the running values for it, line by line, down to the moment a loop goes round once too often.

A trace table records the value of each variable as each line of an algorithm runs. A variable is a named place that holds a value. That record lets you find the output, check that the algorithm works, or find a logic error, a mistake that makes it give the wrong answer. It has one column for each variable and one column for output. A new row goes in each time something changes. Every course sets questions like these, and the method is the same on all of them. It is not a truth table. A truth table lists the inputs to a logic gate and the output each combination gives, which is a different topic altogether. Two explanations of a trace table. A says it is used to check the variables give the right output, and to find bugs. B says it records each variable's value as each line runs, so the output and any bug can be found. Which explanation, A or B, says how a trace table works, not only what it is for? B. A gives the purpose but not the method. B names the mechanism, tracking variables. One examiner's report on this question says: "While some responses achieved both marks for a well-linked explanation, there were many that got trace tables confused with truth tables." And: "Most correct responses mentioned that they are used to check the correct output, or test for bugs, but failed often to explain how, omitting the fact that a trace table tracks variables." The fix is to say what it does and how it does it: a trace table records the value of each variable as each line runs.

The first algorithm to trace is a counted loop, with columns for total, count and output. Line one sets total to nought. The loop starts with count as one, and total becomes nought plus one, which is one. When count is two, what value is in total once that pass ends? Three. Total was one, and adding two makes three. Now carry on for count three and count four: what does total reach, and what is output? Count three makes total six, and count four makes it ten. The loop ends there, and ten is output once, after the loop. That walk used four habits: one column per variable, one line at a time, check the condition every pass, and output only when an output line runs.

This time the output line sits inside the loop, so it runs on every pass. Before each pass, check the condition out loud: is number less than six? Write the answer down, yes or no. Number starts at one. One is less than six, so output two, and number becomes two. Keep going: what is the full output, and on which value of number does the loop stop? Two, four, six, eight, ten. When number reaches six, six is not less than six, so the loop stops with no sixth output. A report on a different paper records this: "When candidates attempted the question, it was noticeable that many iterated the loop too many times and traced number from one to seven." The way to avoid it is the check, written down on every pass, including the last one, where the answer is no. Output goes where the output line is. Here it sits inside the loop, so a value appears on every pass. In the counted loop before, the output line sat after the loop, so ten appeared once, at the end. Another examiner's report records a slip on one side of that: "A lot of the incorrect responses didn't identify that the variable was output inside the loop, choosing to only output once the algorithm had finished". The fix for that slip, and for its opposite, writing an output on every line, is the same. Write an output only when an output line runs, wherever that line sits.

In this last algorithm, you cannot tell how many passes it makes until you trace it. x starts at ten and y at three. While x is greater than or equal to y, take y away from x. When the loop ends, output x. Trace it on paper: how many times does the loop run, and what is the output? Ten is at least three, so x becomes seven. Seven is at least three, so x becomes four. Four is at least three, so x becomes one. One is less than three, so the loop stops after three passes, and the output is one. Now, for any two positive whole numbers, what does this algorithm work out? What is left over when x is divided by y, the remainder. Ten divided by three leaves one. One examiner's report records two slips in tables like these: "Mistakes tended to be with identifying the line number where each change occurred or outputting values that were not actually output, for example minus one." The fix: a value sitting in a variable is not output, and only an output line puts something in the output column. Line numbers help you keep your place, so write them when the question asks. And keep going to the end. A new row for every change can feel repetitive, but a trace that stops early never reaches the final value.

Four habits ran through every trace, and these questions put them to work on fresh loops. What does a trace table record, and when does a new row go in? The value of each variable, and a new row each time a line changes one. Now: count starts at one; while count is less than four, output count, then add one. Output? One, two, three. When count is four, four is not less than four, so the loop stops. A different loop runs five passes, output line after END WHILE. How many outputs? One. The output line runs once, after the loop has finished, however many passes there were. One more: in the bank statement, which column of a trace table is like the balance? Each variable's column. It holds the value after every change, the way the balance does after every payment.

This video now sits in the chapter list. Leave a thumbs up as your sign you have got this down, so there is no need to watch it twice; a video without one is still on your list. If it is still shaky, save it, and come back for a second viewing; tracing often lands the second time through.

Next in the chapter: the video on which algorithm is more efficient, counting the steps each one takes. Hopefully that's next in your feed, but if not, search for ScholaFly C S ten, oh eight.

Every other video is on scholafly.com too, easy to search by video code or by keyword. Whatever you're revising, go there and have a look, or, watch the next video.

Related terms

For: Edexcel GCSE 1CP2, OCR GCSE J277, AQA GCSE 8525

On the specification

BoardSpecStatement
Edexcel GCSE 1CP21.2.4Determine the correct output of an algorithm for a given data set and use a trace table to find what a variable holds at a given point.
OCR GCSE J2772.1.2Designing, creating and refining algorithms
AQA GCSE 8525missingthe plan names no spec point for this board
For teachers

This GCSE Computer Science lesson teaches trace tables. By the end, students should be able to use a trace table to follow an algorithm line by line, recording each change to each variable and every output exactly where it happens, and use it to state what a variable holds at a given point and what the algorithm outputs. It works through four worked examples and the mistakes examiners report.