Trace Tables
- Trace tables are used to follow algorithms and make sure they perform the required task correctly. Test data is usually used in conjunction with a trace table to ensure the correctness of the algorithm. Manually tracing an algorithm with test data in this way is known as a dry run
- Trace tables can be used with flowcharts or pseudocode or even real code if necessary
- Trace tables can also be used to discover the purpose of an algorithm by showing output data and intermediary steps
- Trace tables record the state of the algorithm at each step or iteration. The state includes all variables that impact the algorithms output as well as the output itself
- A trace table is composed of columns where each variable and the output is a column
- Whenever a value changes or an output is produced the relevant column and row is updated to reflect the change
Trace Table Walkthrough
- Below is a flowchart to determine the highest number of 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 an older number then it is replaced
- Once all ten numbers are entered, the algorithm outputs which number was the highest
- Example test data to be used is: 4, 3, 7, 1, 8, 3, 6, 9, 12, 10
Figure 1: A flowchart to determine the highest of ten user entered numbers
|
Trace table for Figure 1: Highest number |
|||
|
Count |
Highest |
Number |
Output |
|
1 |
Enter ten numbers |
||
|
4 |
Enter your first number |
||
|
2 |
3 |
Enter your next number |
|
|
3 |
7 |
7 |
|
|
4 |
1 |
||
|
5 |
8 |
8 |
|
|
6 |
3 |
||
|
7 |
6 |
||
|
8 |
9 |
9 |
|
|
9 |
12 |
12 |
|
|
10 |
10 |
12 is your highest number |
|
Exam Tip
- When asked to identify the purpose of an algorithm in the exam, the variables listed will often be a single letter rather than a meaningful identifier
Worked example
The flowchart represents an algorithm. The algorithm will terminate if –1 is entered.
Complete the trace table for the input data: 50, 75, 99, 28, 82, 150, –1, 672, 80
[4]
|
Value |
Diff1 |
Diff2 |
Output |
[1] for each correct column
|
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 |
