Ch 4 · 7 Algorithm Design: Trace Tables, Errors and Writing Algorithms · IGCSE Computer Science 0478
Topic 4 of 4 in Algorithm Design and Problem-Solving — IGCSE Computer Science 0478 — 39 lessons.
Introduction
A dry run means working through an algorithm by hand, as the computer would, recording every change in a trace table. It is the best way to understand an algorithm and to find its bugs. (Syllabus topic 7, outcomes 7–9.)
Key ideas — Trace tables
A trace table has a column for each variable, plus columns for outputs (and user prompts). Work through the algorithm one line at a time. Write a new value in a column only when it changes, moving down a row as the algorithm progresses.
🧑🏫 Teacher's explanation
Imagine you are following a recipe to bake a cake, but instead of just looking at the final cake, you write down exactly how many grams of flour you add every time you pick up the scoop. A trace table is like that logbook. It is a manual way to 'run' a computer program on paper to see exactly how the values of variables change step-by-step.
📖 Definitions
🔍 Worked example — Easy
Trace the following algorithm for input values: 5, 10, 3.
🔍 Worked example — Standard
Trace the following algorithm for input values: 2, 4, 6.
🔍 Worked example — Exam-style
An algorithm is intended to find the maximum value in a list of numbers. The input is: 12, 45, 7, 23.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Trace the following pseudocode for the input: 10, 5, -2.
Key ideas — Identifying and correcting errors
Common errors in given algorithms:
🧑🏫 Teacher's explanation
Think of debugging an algorithm like following a recipe that went wrong. If you are making a cake and the cake comes out too salty, you don't just say 'the cake is bad'; you look at the steps. Did you add too much salt? Did you forget to add flour? Did you use sugar instead of salt? In computer science, we do the same thing using a 'dry-run' or a trace table.
📖 Definitions
🔍 Worked example — Easy
Identify the error in this pseudocode intended to find the average of three numbers:
🔍 Worked example — Standard
Trace the following algorithm for an array A = [12, 5, 20] and find the value of Max at the end:
🔍 Worked example — Exam-style
An algorithm is meant to count how many students passed (score ≥ 50) in a class of 5 students. The code is:
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Identify one potential logic error that could occur if the user enters a non-numeric character, and explain how the programmer could use a trace table to detect it. [3 marks]
Key ideas — Writing and amending algorithms
Exam questions ask you to write algorithms in pseudocode (or, in the 15-mark scenario question, pseudocode or program code in Python, Visual Basic or Java), or as flowcharts.
🧑🏫 Teacher's explanation
Think of writing an algorithm like writing a recipe. If you just say "cook the pasta," it is a bad recipe because it doesn't say how much water, how much salt, or for how long. A computer is the ultimate literalist; it needs precise instructions. If you say "add salt until it tastes right," the computer will crash because it doesn't have taste buds.
📖 Definitions
🔍 Worked example — Easy
Write pseudocode to find the sum of integers from 1 to 5.
🔍 Worked example — Standard
An algorithm finds the maximum value in an array Numbers of size 10. The current code is: FOR i <- 1 TO 10 IF Numbers[i] > Max THEN Max <- Numbers[i] ENDIF NEXT i Amend this to also count how many times the maximum value appears.
🔍 Worked example — Exam-style
Trace the following algorithm for the given input: DECLARE x, y : INTEGER INPUT x INPUT y IF x > y THEN OUTPUT x - y ELSE OUTPUT y - x ENDIF Input values: x = 5, y = 12
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
DECLARE Total : REAL DECLARE Num : REAL Total <- 0 FOR i <- 1 TO 10 INPUT Num Total <- Total + Num NEXT i OUTPUT Total / 10
Worked example
🔍 Worked example — Easy
Complete the trace table for the following snippet:
🔍 Worked example — Standard
Identify the error in this algorithm intended to calculate the sum of numbers from 1 to 5:
🔍 Worked example — Exam-style
A programmer wants to find the average of 3 numbers. They write:
⚠️ Common errors
Common mistakes
Practice
Product ← 1 FOR Index ← 1 TO 3 INPUT Value Product ← Product * Value NEXT Index OUTPUT Product