Learning Objectives
By the end of this lesson, you will be able to:
- Explainwhat a trace table is and why it is used
- Describethe rules for completing a trace table, including how variables and outputs are recorded
- Completea trace table for a given algorithm
- Dry-runan algorithm line by line, updating the state of each variable
- Identifylogic errors in an algorithm by using a trace table
- Discoverthe purpose of an algorithm by tracing its execution
Key Terms
Trace table
A table used to test algorithms and programs for logic errors. It records the state of each variable at every step of execution.
Dry-run
Executing an algorithm manually, step by step, on paper or in a trace table — without using a computer.
Logic error
An error in the logic of an algorithm that causes it to produce incorrect results. Trace tables are excellent at tracking these down.
Variable
A named storage location in a program. Each variable in the algorithm should have its own column in the trace table.
Iteration
A single pass through a loop. Each iteration of a loop typically adds one or more new rows to the trace table.
Output
Any value displayed or produced by the algorithm. The output column in the trace table records what the program prints at each step.
1. What is a Trace Table?
Atrace tableis used to test algorithms and programs forlogic errorsthat appear when an algorithm or program executes. Trace tables can be used with flowcharts, pseudocode, or program code.
A trace table can be used to:
- Discover the purpose of an algorithm by showing output data and intermediary steps
- Record the state of the algorithm at each step or iteration
- Check inputs, outputs, variables and processes for the correct value when a stage is completed
1.1 How to Complete a Trace Table
Tracing executionis a vital skill for understanding program flow and testing the accuracy of an algorithm for logic. It involves examining a printed extract of program code and running through the program:
Step by step
Take each line at a time and write the current state of each variable in a trace table.
Record output
Note down any output the program produces.
One column per variable
Each variable present in the program should have its own column in the trace table.
New row on change
A new row should be added under any column if the state of a variable changes.
Why trace tables matter
Trace tables are anexcellent way to track down logic errorsin a problem. By working through the algorithm step by step, you can see exactly where the program goes wrong and what value is causing the problem.
Activity 1: Trace Table Rules
Answer the following questions about trace tables:
- What is the main purpose of a trace table?
- How many columns should a trace table have?
- When should a new row be added to a trace table?
- What kinds of algorithms can a trace table be used with?
Solution:
- Purpose:To test algorithms and programs for logic errors, record the state of the algorithm at each step, and discover the purpose of an algorithm by showing output data and intermediary steps.
- Number of columns:One column for each variable in the program, plus a column for output.
- New row:A new row should be added when the state of any variable changes.
- Compatible algorithms:Trace tables can be used with flowcharts, pseudocode, or program code.
Check Your Understanding: Trace Table Basics
1. Define the term "trace table". [2 marks]
Answer
- [1 mark]A table used to test algorithms and programs for logic errors
- [1 mark]It records the state of each variable at every step or iteration of execution
2. Describe how a trace table is used to trace the execution of an algorithm. [3 marks]
Answer
- [1 mark]Each line of the algorithm is executed step by step
- [1 mark]The current state of each variable is written into the trace table
- [1 mark]Any output the program produces is also noted down, and a new row is added whenever a variable changes
3. Explain why trace tables are useful for finding logic errors. [3 marks]
Answer
- [1 mark]A trace table shows the value of every variable at every step
- [1 mark]This makes it easy to spot the exact point where a variable takes an unexpected value
- [1 mark]By identifying the step where the logic goes wrong, the programmer can find and fix the error
4. What types of algorithm representation can be used with a trace table? [3 marks]
Answer
- [1 mark]Flowcharts
- [1 mark]Pseudocode
- [1 mark]Program code
5. Why is it good practice to record outputs in a trace table? [2 marks]
Answer
- [1 mark]Recording outputs shows exactly what the program produces at each stage
- [1 mark]It helps the programmer compare the actual output against the expected output to verify correctness
2. Worked Example: Factorial Program
Let's trace through the following algorithm, which calculates the factorial of a number entered by the user. If the user enters5, the program outputs120(since 1 × 2 × 3 × 4 × 5 = 120).
Program Code
Output Window
What is this program doing?
It is outputting thefactorialof the number entered. Factorial 5 = 1 × 2 × 3 × 4 × 5 =120.
2.1 Complete Trace Table
The table below traces through the program step by step. Each time a variable changes, a new row is added. Values highlighted inambershow where a variable was updated.
| number | counter | total | output |
|---|---|---|---|
| 5 | |||
| 1 | |||
| 1 | |||
| 1 | |||
| 2 | |||
| 2 | |||
| 3 | |||
| 6 | |||
| 4 | |||
| 24 | |||
| 5 | |||
| 120 | |||
| 6 | |||
| 120 |
Reading the trace table
- Row 1:The user enters 5, sonumber = 5
- Row 2:totalis initialised to 1
- Row 3:The loop starts, socounter = 1
- Row 4:total = total * counter = 1 * 1 = 1
- Row 5:Loop repeats,counter = 2
- Row 6:total = 1 * 2 = 2
- ... and so on untilcountergoes past 5
- Final row:The loop ends whencounter = 6(which is > number), and the program outputstotal = 120
Interactive: Step Through the Trace Table
ClickNext Stepto walk through the algorithm one line at a time and watch the trace table fill in.
| number | counter | total | output |
|---|
Step 0:Ready to begin. Click "Next Step" to trace the first line of code.
Activity 2: Complete the Trace Table
Trace through the same factorial algorithm, but this time the user enters4. Complete the trace table:
| number | counter | total | output |
|---|---|---|---|
| 4 | |||
| 1 | |||
| 1 | |||
| ? | |||
| 2 | |||
| ? | |||
| 3 | |||
| ? | |||
| 4 | |||
| ? | |||
| 5 | |||
| ? |
Solution:
| number | counter | total | output |
|---|---|---|---|
| 4 | |||
| 1 | |||
| 1 | |||
| 1 | |||
| 2 | |||
| 2 | |||
| 3 | |||
| 6 | |||
| 4 | |||
| 24 | |||
| 5 | |||
| 24 |
Answer:4! = 24
Check Your Understanding: Factorial Trace
1. In the factorial trace table (number = 5), what is the value oftotalafter the third iteration of the loop? [1 mark]
Answer
- [1 mark]6— after three iterations, total = 1 × 2 × 3 = 6
2. Why does the loop stop whencounter = 6rather thancounter = 5? [2 marks]
Answer
- [1 mark]The loop runs forcounter = 1 to number, so it processes counter = 1, 2, 3, 4, 5 (5 iterations)
- [1 mark]After the 5th iteration,counterincrements to 6, which is greater thannumber(5), so the loop terminates
3. What does this algorithm do? [2 marks]
Answer
- [1 mark]The algorithm calculates the factorial of a number entered by the user
- [1 mark]It multiplies all whole numbers from 1 up to that number together and outputs the result
4. If the user entered 6, what would the final output be? Show your working. [2 marks]
Answer
- [1 mark]6! = 1 × 2 × 3 × 4 × 5 × 6
- [1 mark]=720
5. If the user entered 1, how many times would the loop run and what would the output be? [2 marks]
Answer
- [1 mark]The loop runs1 time(counter = 1)
- [1 mark]1! = 1, so the output is1
3. Trace Table Walkthrough: Highest Number
Below is a flowchart to determine thehighest numberof ten user-entered numbers. The algorithm prompts the user to enter the first number, which automatically becomes the highest number entered. The user is then prompted to enter nine more numbers. If a new number is higher than the current highest, it replaces it. Once all ten numbers have been entered, the algorithm outputs which number was the highest.
Example test data
4, 3, 7, 1, 8, 3, 6, 9, 12, 10
3.1 Trace Table: Highest Number
| Count | HighestNumber | Output |
|---|---|---|
| 1 | Enter ten numbers | |
| 4 | Enter your first number | |
| 2 | 4 | Enter your next number |
| 3 | 7 | |
| 4 | 7 | |
| 5 | 8 | |
| 6 | 8 | |
| 7 | 8 | |
| 8 | 9 | |
| 9 | 12 | |
| 10 | 12 | 12 is your highest number |
Understanding the trace
- The first number (4) becomes the starting highest number
- 3 is not higher than 4, so highest stays at 4
- 7 is higher than 4, so highest becomes 7
- 1 is not higher, highest stays at 7
- 8 is higher than 7, so highest becomes 8
- 3 is not higher, highest stays at 8
- 6 is not higher, highest stays at 8
- 9 is higher than 8, so highest becomes 9
- 12 is higher than 9, so highest becomes 12
- 10 is not higher than 12, so highest stays at 12
- After 10 numbers, the output is:12 is your highest number
Check Your Understanding: Highest Number
1. What is the purpose of this algorithm? [2 marks]
Answer
- [1 mark]To find and output the highest number out of ten numbers entered by the user
- [1 mark]The first number becomes the starting highest, and each subsequent number replaces it only if it is higher
2. Why is the first number automatically assigned as the highest number? [2 marks]
Answer
- [1 mark]Because there's nothing to compare it to yet — the algorithm needs a starting value for "highest"
- [1 mark]Using the first number as the initial highest value means every subsequent number can be compared against it
3. Using the trace table, identify at which count the highest number changed from 9 to 12. [1 mark]
Answer
- [1 mark]At count9(when the number 12 was entered)
4. If the input data was5, 8, 3, 9, 2, 7, 1, 6, 4, 10, what would the final highest number be? [1 mark]
Answer
- [1 mark]10— the highest number in the list is 10, and it is the last number entered
4. Worked Example: Diff1 and Diff2
The flowchart represents an algorithm. The algorithm will terminate if-1is entered.
Complete the trace table for the input data:50, 75, 99, 28, 82, 150, -1, 672, 80
Algorithm summary
- Accepts input values
- Computes two differences:Diff1andDiff2
- Classifies each value asExtreme,Normal, orAbnormal
- Terminates when -1 is entered
4.1 Completed Trace Table
| Value | Diff1 | Diff2 | Output |
|---|---|---|---|
| 50 | 50 | 0 | Accept: Extreme |
| 75 | 25 | 25 | Accept: Normal |
| 99 | 1 | 49 | Accept: Normal |
| 28 | Reject: Abnormal | ||
| 82 | 18 | 32 | Accept: Normal |
| 150 | Reject: Abnormal | ||
| -1 | Terminate |
Reading the trace
- 50:Diff1 = 50 (first value), Diff2 = 0 — accepted as extreme (first value)
- 75:Diff1 = 25 (75−50), Diff2 = 25 — accepted as normal
- 99:Diff1 = 1 (100−99), Diff2 = 49 (99−50) — accepted as normal
- 28:rejected as abnormal (fails the algorithm's rules)
- 82:Diff1 = 18 (100−82), Diff2 = 32 (82−50) — accepted as normal
- 150:rejected as abnormal (out of range)
- -1:terminates the algorithm — no further values are processed (672 and 80 are not traced)
Notice
Once -1 is entered, the algorithmterminates, so the values 672 and 80 arenever processedand do not appear in the trace table. This is a key part of understanding how the algorithm works.
Activity 3: Trace the Running Total
Consider this algorithm:
Complete the trace table:
| i | total | output |
|---|---|---|
| 0 | ||
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| ? |
Solution:
| i | total | output |
|---|---|---|
| 0 | ||
| 1 | 1 | |
| 2 | 3 | |
| 3 | 6 | |
| 4 | 10 | |
| 5 | 15 | |
| 15 |
Output:15 (the sum of 1 + 2 + 3 + 4 + 5)
Check Your Understanding: Diff Trace
1. Why do values 672 and 80 not appear in the Diff trace table? [2 marks]
Answer
- [1 mark]The algorithm terminates when -1 is entered
- [1 mark]Since -1 appears before 672 and 80 in the input list, the algorithm stops before reaching them
2. Explain why 50 was classified as "Extreme" and 75 as "Normal". [3 marks]
Answer
- [1 mark]50 was the first value entered, so it set the base for comparison (Diff1 = 50, Diff2 = 0)
- [1 mark]75 fell within the acceptable range relative to 50 (Diff1 = 25, Diff2 = 25), so it was a normal value
- [1 mark]Values that fall outside the algorithm's acceptable range (like 28 or 150) are rejected as abnormal
3. What is the purpose of the Diff1 and Diff2 values? [2 marks]
Answer
- [1 mark]They are used to measure how far a value is from key reference points
- [1 mark]Based on these differences, the algorithm decides whether to accept each value as Extreme or Normal, or reject it as Abnormal
4. What is the final output of this algorithm? [1 mark]
Answer
- [1 mark]The algorithm terminates without producing a single final output value — it produces classification outputs ("Accept: Extreme", "Accept: Normal", "Reject: Abnormal") for each value it processes
Key Takeaways
- Atrace tableis used to test algorithms and programs for logic errors that appear when the algorithm or program executes.
- Trace tables can be used withflowcharts, pseudocode, or program code.
- Each variable in the algorithm should have itsown columnin the trace table, plus a column for output.
- Anew rowshould be added whenever the state of a variable changes.
- Trace tables are used todiscover the purposeof an algorithm,record the stateat each step, andcheckinputs, outputs, variables and processes.
- Trace tables are anexcellent way to track down logic errors— by following the algorithm step by step, you can see exactly where the values go wrong.
- In the factorial example, the trace table shows howtotalaccumulates the product 1 × 2 × 3 × 4 × 5 = 120.
- In the highest number algorithm, the trace table shows when theHighestNumbervariable is updated as each new number is entered.
- In the Diff1/Diff2 example, the algorithmterminateswhen -1 is entered, so later values are never processed.
- Recording output in the trace table helps compare theactual outputagainst theexpected outputto verify correctness.
Question Bank
1. Define a trace table and explain its purpose. [4 marks]
Answer
- [2 marks]A trace table is a table used to test algorithms and programs for logic errors that appear when the algorithm executes
- [1 mark]It records the state of each variable at every step or iteration
- [1 mark]It is used to discover the purpose of an algorithm, record state, and check that inputs, outputs and processes are correct
2. A program contains variablesa,bandc. How many columns should the trace table have and what should they be? [2 marks]
Answer
- [1 mark]4 columns: one for each variable (a, b, c) plus a column for output
- [1 mark]Each variable has its own column, and a new row is added whenever any variable changes
3. Complete the trace table for this algorithm: [6 marks]
total = 0
for i = 1 to 4
total = total + i * 2
next i
output(total)
Answer
| i | total | output |
|---|---|---|
| 0 | ||
| 1 | 2 | |
| 2 | 6 | |
| 3 | 12 | |
| 4 | 20 | |
| 20 |
Marking:Correct total values (2, 6, 12, 20), correct final output (20), correct structure.
4. Explain why it is important to record output values in a trace table, not just variable values. [3 marks]
Answer
- [1 mark]Recording output shows exactly what the program produces at each stage
- [1 mark]It helps the programmer compare actual output against expected output to verify correctness
- [1 mark]Without recording outputs, the programmer cannot fully verify the program works as intended — only the internal variable states would be visible
5. A trace table for a sorting algorithm has 8 rows. What does this tell you about the algorithm? [2 marks]
Answer
- [1 mark]It tells you the algorithm performed 8 distinct steps or iterations (each row represents a change in a variable)
- [1 mark]This gives insight into how many operations or passes the algorithm needs to complete its task
6. A trace table shows a variable that never changes throughout the algorithm's execution. What might this indicate? [2 marks]
Answer
- [1 mark]It might indicate a constant value that is used for comparison or reference
- [1 mark]It could also indicate a logic error — perhaps the variable was supposed to be updated but the update statement is missing or has a mistake
7. Trace through this algorithm with inputn = 3: [5 marks]
result = 1
for i = 1 to n
result = result * i
next i
output(result)
What is the final output?
Answer
| i | result | output |
|---|---|---|
| 1 | ||
| 1 | 1 | |
| 2 | 2 | |
| 3 | 6 | |
| 6 |
Final output:6(this is 3! = 1 × 2 × 3 = 6)
8. Describe two ways in which a trace table can help a programmer identify and fix errors in an algorithm. [4 marks]
Answer
- [2 marks]A trace table records the value of every variable at every step, so the programmer can spot the exact moment where a variable takes an unexpected value
- [2 marks]It also shows output values, allowing the programmer to compare actual output against expected output and identify where the logic produces incorrect results