Complete a trace table to document a dry-run of an algorithm

Algorithm Design & Problem‑Solving – Trace Tables (Cambridge IGCSE 0478)

1. Programme‑Development Life‑Cycle (PDLC)

Stage	What is Done	Typical IGCSE Example
Analysis	Identify the problem, required inputs, expected outputs and any constraints.	“Calculate the sum of the first n positive integers”. Input = n, Output = sum.
Design	Select a standard solution method (flowchart, structure diagram, pseudocode) and decide which control structures are needed.	Use a WHILE loop (iteration) or a FOR loop (iteration) to add 1…n.
Implementation (Coding)	Write the solution in pseudocode (or a programming language).	See “Sample Algorithm – Sum to n”.
Testing & Validation	Run the algorithm with a range of test data (including boundary and error cases) to ensure the *right* problem is being solved.	Test with n = 0, n = 1, n = 5 and with a negative value to trigger validation.
Verification	Check that the written solution matches the design and that the output is mathematically correct (the *right* answer).	Compare the final sum with the formula n(n+1)/2.

2. Validation vs. Verification

• Validation – “Am I solving the right problem?”
  • Example: IF n < 1 THEN OUTPUT “Error – n must be positive” ; STOP END IF
  • Test with out‑of‑range data (e.g. n = -3).
• Verification – “Am I solving the problem correctly?”
  • Example: after the loop, confirm sum = n(n+1)/2 for several values.
  • Check the algorithm against a flowchart or structure diagram.

3. What is a Trace Table?

A trace table records the values of every relevant variable after each statement of an algorithm is executed. It is the primary tool for:

• Dry‑running (testing) before any code is written.
• Answering exam questions that require a step‑by‑step explanation.
• Demonstrating verification of the algorithm.

Key Columns

Column	Purpose
Step	Sequential number of the executed statement.
Statement Executed	The line of pseudocode being processed.
Variable(s)	Current contents of each variable after the statement.
Output	Any value printed or returned at that step.
Condition (if applicable)	Result of a Boolean test – “true” or “false”.

4. Data‑Type Reminder (IGCSE 0478 – AO1)

Variable	Purpose	Data type	Declaration (pseudocode)
n	Upper limit supplied by the user	INTEGER	DECLARE n : INTEGER
i	Loop counter	INTEGER	DECLARE i : INTEGER
sum	Running total	INTEGER	DECLARE sum : INTEGER
arr[ ]	Array of integers (example)	INTEGER ARRAY	DECLARE arr[10] : INTEGER
ch	Single character	CHARACTER	DECLARE ch : CHARACTER

5. Standard Methods of Solution (AO2)

• Flowchart – visual representation of the sequence, selection and iteration.
• Structure diagram – hierarchical view of modules/procedures.
• Pseudocode – language‑independent description of the algorithm.

6. Sample Algorithm – Summing the First n Integers

1.  INPUT n
2.  IF n < 1 THEN OUTPUT “Error – n must be positive” ; STOP END IF   // validation
3.  sum ← 0
4.  i ← 1
5.  WHILE i ≤ n DO
6.      sum ← sum + i
7.      i ← i + 1
8.  END WHILE
9.  OUTPUT sum

Dry‑Run (Trace Table) – n = 4

Step	Statement	i	sum	Output	Condition
1	INPUT n	–	–	–	–
2	IF n < 1 … (false)	–	–	–	false
3	sum ← 0	–	0	–	–
4	i ← 1	1	0	–	–
5	i ≤ n ? (1 ≤ 4)	1	0	–	true
6	sum ← sum + i	1	1	–	–
7	i ← i + 1	2	1	–	–
8	i ≤ n ? (2 ≤ 4)	2	1	–	true
9	sum ← sum + i	2	3	–	–
10	i ← i + 1	3	3	–	–
11	i ≤ n ? (3 ≤ 4)	3	3	–	true
12	sum ← sum + i	3	6	–	–
13	i ← i + 1	4	6	–	–
14	i ≤ n ? (4 ≤ 4)	4	6	–	true
15	sum ← sum + i	4	10	–	–
16	i ← i + 1	5	10	–	–
17	i ≤ n ? (5 ≤ 4)	5	10	–	false
18	OUTPUT sum	5	10	10	–

Practice – Complete the Trace Table (n = 5)

Fill in the missing values. The final sum must be 15.

Step	Statement	i	sum	Output	Condition
1	INPUT n	–	–	–	–
2	IF n < 1 … (false)	–	–	–	false
3	sum ← 0	–	0	–	–
4	i ← 1	1	0	–	–
5	i ≤ n ? (1 ≤ 5)	1	0	–	true
6	sum ← sum + i	1	1	–	–
7	i ← i + 1	2	1	–	–
8	i ≤ n ? (2 ≤ 5)	2	1	–	true
9	sum ← sum + i	2	3	–	–
10	i ← i + 1	3	3	–	–
11	i ≤ n ? (3 ≤ 5)	3	3	–	true
12	sum ← sum + i	3	6	–	–
13	i ← i + 1	4	6	–	–
14	i ≤ n ? (4 ≤ 5)	4	6	–	true
15	sum ← sum + i	4	10	–	–
16	i ← i + 1	5	10	–	–
17	i ≤ n ? (5 ≤ 5)	5	10	–	true
18	sum ← sum + i	5	15	–	–
19	i ← i + 1	6	15	–	–
20	i ≤ n ? (6 ≤ 5)	6	15	–	false
21	OUTPUT sum	6	15	15	–

7. Other Mandatory Algorithms (AO2)

Each of the following can be expressed as a flowchart, structure diagram and pseudocode. Use the same trace‑table technique to test them.

7.1 Linear Search (Find first occurrence of a value in an array)

1. INPUT size, target
2. FOR i ← 1 TO size DO
3.     INPUT arr[i]
4. END FOR
5. pos ← 0
6. i ← 1
7. WHILE i ≤ size AND pos = 0 DO
8.     IF arr[i] = target THEN pos ← i END IF
9.     i ← i + 1
10. END WHILE
11. IF pos = 0 THEN OUTPUT “Not found” ELSE OUTPUT “Found at”, pos END IF

7.2 Bubble Sort (Ascending order)

1. INPUT size
2. FOR i ← 1 TO size DO INPUT arr[i] END FOR
3. swapped ← true
4. WHILE swapped DO
5.     swapped ← false
6.     FOR i ← 1 TO size‑1 DO
7.         IF arr[i] > arr[i+1] THEN
8.             temp ← arr[i]
9.             arr[i] ← arr[i+1]
10.            arr[i+1] ← temp
11.            swapped ← true
12.        END IF
13.    END FOR
14. END WHILE
15. OUTPUT arr[1] … arr[size]

7.3 Max, Min & Average of a list

1. INPUT size
2. FOR i ← 1 TO size DO INPUT arr[i] END FOR
3. max ← arr[1]; min ← arr[1]; total ← 0
4. FOR i ← 1 TO size DO
5.     IF arr[i] > max THEN max ← arr[i] END IF
6.     IF arr[i] < min THEN min ← arr[i] END IF
7.     total ← total + arr[i]
8. END FOR
9. avg ← total / size
10. OUTPUT max, min, avg

8. Selection & Iteration Structures (AO1 & AO2)

• Simple selection – IF … THEN … END IF or IF … THEN … ELSE … END IF
• Multiple selection – CASE … OF … END CASE
• Simple iteration – WHILE … DO … END WHILE or FOR i ← a TO b DO … END FOR
• Nested selection/iteration – e.g. a FOR loop inside a WHILE loop (useful for 2‑D arrays).

Example of Nested Loops (2‑D array total)

1. INPUT rows, cols
2. FOR r ← 1 TO rows DO
3.     FOR c ← 1 TO cols DO
4.         INPUT matrix[r][c]
5.     END FOR
6. END FOR
7. total ← 0
8. FOR r ← 1 TO rows DO
9.     FOR c ← 1 TO cols DO
10.        total ← total + matrix[r][c]
11.    END FOR
12. END FOR
13. OUTPUT total

9. Procedures / Functions (AO2)

Procedures help to organise code, limit the scope of variables and support re‑use.

PROCEDURE SumToN(n)
    IF n < 1 THEN RETURN 0 END IF
    sum ← 0
    i ← 1
    WHILE i ≤ n DO
        sum ← sum + i
        i ← i + 1
    END WHILE
    RETURN sum
END PROCEDURE

--- Main program ---
INPUT n
OUTPUT SumToN(n)

• Parameters are passed by value (the procedure works with a copy of n).
• Variables sum and i are local – they disappear when the procedure ends.

10. File Handling (AO2)

IGCSE does not require a specific language, but the standard operations are:

• OPEN file FOR INPUT – open an existing text file for reading.
• OPEN file FOR OUTPUT – create a new text file (or overwrite) for writing.
• READ file, variable – read the next data item.
• WRITE file, variable – write a data item.
• CLOSE file – release the file.

OPEN "scores.txt" FOR INPUT
READ file, n               // number of scores
total ← 0
FOR i ← 1 TO n DO
    READ file, score
    total ← total + score
END FOR
CLOSE file
average ← total / n
OUTPUT "Average =", average

11. Library Routines (AO1)

Routine	Purpose	Typical Use in IGCSE
ROUND(x)	Round to nearest integer	Display a rounded average
RANDOM()	Generate a pseudo‑random number between 0 and 1	Simulate dice rolls, Monte‑Carlo tests
LEN(s)	Length of a string	Validate input length
SUBSTR(s, start, length)	Extract part of a string	Parse a fixed‑format record
UPPER(s) / LOWER(s)	Change case	Case‑insensitive comparisons

12. Boolean Logic & Logic Gates (AO1)

• Boolean expressions are built from relational operators (=, ≠, <, ≤, >, ≥) and the logical operators AND, OR, NOT.
• In a flowchart, the condition box represents a Boolean expression; the true/false arrows correspond to the two outputs of an AND/OR gate.

Example – Loop with Two Conditions

Continue while i ≤ n **and** i MOD 2 = 0 (process only even numbers).

WHILE i ≤ n AND i MOD 2 = 0 DO
    ….
END WHILE

i ≤ n	i MOD 2 = 0	Loop continues?
true	true	true
true	false	false
false	true	false
false	false	false

13. Databases – Single‑Table Design (AO1)

IGCSE expects you to understand the concepts of a table, primary key and basic SQL.

13.1 Table Design Example – “Students”

Field (column)	Data type	Purpose	Primary Key?
StudentID	INTEGER	Unique identifier	Yes
Name	CHAR(30)	Student’s full name	No
Age	INTEGER	Age in years	No
Score	INTEGER	Exam score (0‑100)	No

13.2 Basic SQL Statements

-- Create the table
CREATE TABLE Students (
    StudentID INTEGER PRIMARY KEY,
    Name CHAR(30),
    Age INTEGER,
    Score INTEGER
);

-- Insert a record
INSERT INTO Students VALUES (101, 'Ali Khan', 16, 78);

-- Retrieve all scores above 70
SELECT StudentID, Name, Score FROM Students WHERE Score > 70;

-- Find the average score
SELECT AVG(Score) FROM Students;

14. Quick Audit of the Revised Notes (Against the Cambridge Syllabus)

Syllabus block	Coverage in these notes	Remaining gaps (if any)
1‑6 Computer systems	Brief reminder of data types; not a full coverage of binary, hardware, networking, security, emerging tech.	Add a short “Computer‑systems snapshot” section if time permits.
7 Algorithm design & problem‑solving	PDLC, validation/verification, flowchart/structure‑diagram/pseudocode, trace tables, multiple mandatory algorithms.	None – fully aligned.
8 Programming	Variables, data types, I/O, selection, iteration (including nested), arrays, procedures, file handling, library routines.	None – covers all required constructs.
9 Databases	Single‑table design, primary key, example SQL statements.	None – meets AO1 requirements.
10 Boolean logic	Truth tables, logic‑gate link, Boolean expressions used in loop conditions.	None – adequate for AO1.
Assessment‑objective alignment	Explicit AO1, AO2 and AO3 links throughout (knowledge, application, evaluation).	None.

15. Tips for Completing a Trace Table (AO3 – Evaluation)

1. Write down the initial values of **all** variables before the first step.
2. Update **only** the variables that the current statement changes.
3. When a condition is evaluated, record “true” or “false” in a separate column – this determines the next line.
4. Keep the table tidy: one row = one statement execution.
5. After the dry‑run, verify the final output:
   • Mathematical formula (e.g., n(n+1)/2).
   • Calculator or spreadsheet check.
6. Test boundary values (n = 1, n = 0) and an out‑of‑range value to practise **validation**.
7. For nested loops, include an extra column for the **inner‑loop counter**.
8. When using procedures, show a separate trace table for the procedure and another for the main program.

16. Suggested Exam‑style Question

Question: Write pseudocode to read a list of m integers, store them in an array, and output the largest and smallest values. Then, using m = 4 and the input values 7, 3, 9, 5, complete the trace table shown.

Answer outline (pseudocode):

1. INPUT m
2. FOR i ← 1 TO m DO INPUT arr[i] END FOR
3. max ← arr[1]; min ← arr[1]
4. FOR i ← 2 TO m DO
5.     IF arr[i] > max THEN max ← arr[i] END IF
6.     IF arr[i] < min THEN min ← arr[i] END IF
7. END FOR
8. OUTPUT "Max =", max, "Min =", min

The trace table would follow the same format as earlier, with columns for i, arr[i], max, min and the condition results for steps 5 and 6.

---

Use these notes to practise building and interpreting trace tables, to link every algorithm to the PDLC, and to ensure you can discuss validation, verification and evaluation – exactly what the Cambridge IGCSE 0478 exam expects.