Computational Thinking, Problem-Solving and Programming
Topic 4 is where you design and trace algorithms. The exam asks you to decompose a problem, write or complete pseudocode, and follow code exactly as written - including code you believe is wrong. Tracing accuracy, not elegance, earns the marks.
Design and thinking
Abstraction removes detail irrelevant to the problem; decomposition splits a problem into sub-problems that can be solved separately; pattern recognition reuses known solutions. Standard constructs: sequence, selection (if/else, case), and iteration (counted loop, while loop, do-while). Subprograms take parameters and return values; every recursive subprogram needs a base case alongside the recursive call.
Algorithms to know
Bubble sort repeatedly compares adjacent pairs and swaps them, stopping early if a pass makes no swaps. Selection sort finds the minimum of the unsorted section and swaps it into place. Linear search works on unsorted data and inspects items one by one; binary search requires sorted data and halves the search space each comparison. Test data should include normal, extreme and invalid cases, and validation checks input before it enters the system.
Worked example
Binary search for 23 in [3, 8, 11, 17, 23, 29, 34, 41], indices 0–7. Middle index 3 holds 17; 17 < 23, so discard the left half. New range 4–7, middle index 5 holds 29; 29 > 23, so discard 5–7. New range 4–4, which holds 23 - found in three comparisons. The array must be sorted first: on unsorted data a binary search does not merely run slowly, it returns the wrong answer.
Traps that cost marks
- Off-by-one errors at loop boundaries; a trace table exposes them.
- Applying binary search to unsorted data.
- Recursion with no base case, causing infinite recursion or a stack overflow.
- Forgetting that a while loop may execute zero times while a do-while always executes at least once.
- Writing a trace table that records only the final value of a variable instead of every change.