Trace Tables, Error Types and Algorithm Evaluation
Trace Tables — Following an Algorithm Step by Step
A trace table lets you follow an algorithm manually, recording the value of every variable at each step. Each column in the table represents a variable (or the output); each row represents the state of the algorithm after one step has executed. Trace tables are the standard method for finding logic errors and for checking that an algorithm produces the correct result for a given set of input data.
The two most common trace-table errors in exams are: (1) adding extra rows for iterations that did not actually happen, and (2) forgetting to update a counter variable on every iteration. One row per state change — no more, no less.
Consider this algorithm in plain-English pseudocode:
1. Set total to 0.
2. Set counter to 1.
3. While counter is less than or equal to 4:
a. Add counter to total.
b. Add 1 to counter.
4. Display total.
Trace table (columns: counter, total, output):
Before loop: counter = 1, total = 0.
Iteration 1: condition 1 ≤ 4 is True. total = 0 + 1 = 1. counter = 2.
Iteration 2: condition 2 ≤ 4 is True. total = 1 + 2 = 3. counter = 3.
Iteration 3: condition 3 ≤ 4 is True. total = 3 + 3 = 6. counter = 4.
Iteration 4: condition 4 ≤ 4 is True. total = 6 + 4 = 10. counter = 5.
Check condition: 5 ≤ 4 is False. Loop ends. Output: 10.
The algorithm sums the integers from 1 to 4, producing 10. Its purpose: sum the integers from 1 to n (where n = 4).
Three Types of Error
Three categories of error can occur in programs. Understanding exactly what each type means is important. A definition that could apply to more than one type will not gain the mark.
A syntax error occurs when the rules of the programming language have been broken. The program cannot run at all — the language processor detects the error before execution begins. A misspelled keyword or a missing bracket are syntax errors. The key definition, word for word: the rules of the programming language have been broken. Avoid saying “a spelling mistake” in isolation — this is too vague and could describe a logic error too.
A logic error occurs when the program runs without crashing but produces incorrect results. The syntax is valid; the code executes; but the outcome is wrong. A common example: using a greater-than sign (>) where a greater-than-or-equal-to sign (≥) was intended, causing the program to exclude a boundary value.
A runtime error occurs while the program is executing. The syntax is valid and the program starts running, but it encounters an operation it cannot complete — such as dividing a number by zero, or attempting to access an index position that does not exist in an array. The program crashes or is forced to stop.
Syntax error example: A student writes dsiplay(score) instead of display(score). The language processor cannot recognise the keyword and refuses to run the program.
Logic error example: A grading program is intended to give a Merit to students scoring 70 or above. The developer writes the condition as “if the score is greater than 70” instead of “greater than or equal to 70”. The program runs without error, but a student with exactly 70 receives Pass instead of Merit — the result is wrong.
Runtime error example: A program divides a student’s total marks by the number of assessments taken. If the student has taken zero assessments (perhaps they are a new enrolment), the program attempts to divide by zero — this is an operation the processor cannot complete, and the program crashes.
Fitness for Purpose and Algorithm Efficiency
An algorithm is fit for purpose if it correctly solves the intended problem for all valid inputs, including boundary values and edge cases. You can check fitness for purpose by using logical reasoning and by running the algorithm with carefully chosen test data.
Even if an algorithm is correct, it may not be efficient. Your specification identifies three measures of efficiency: the number of comparisons made, the number of passes through a loop, and the use of memory.
Efficiency is measured in three ways: (1) number of comparisons — how many times the algorithm checks a condition against a value (important in searching: binary search needs far fewer comparisons than linear search for large datasets); (2) number of passes through a loop — how many times a loop body executes (important in sorting: bubble sort may need many passes); (3) use of memory — how much storage the algorithm needs (important in sorting: merge sort needs extra memory for sub-lists; bubble sort does not).
To evaluate an algorithm, ask three questions:
1. Is it correct? Trace through the algorithm with a normal input, a boundary input (e.g. the minimum or maximum valid value), and an edge case (e.g. an empty list). Does the output match what was expected in every case?
2. Is it efficient? Count the number of comparisons and loop passes for a given input size. If the dataset doubles in size, does the algorithm take twice as long, or much longer? Bubble sort on a list of 100 items needs many more passes than on a list of 10 — the number of passes grows with the size of the problem.
3. Does it use memory wisely? Does the algorithm create large temporary structures (like the sub-lists in merge sort)? On a device with limited RAM — such as an embedded system in a medical device — high memory use could cause problems even if the algorithm is correct.