Programming and Algorithms
The Programming and Algorithms domain tests whether you can express a solution precisely and reason about its behaviour. Expect pseudocode, flowcharts, trace tables, subprograms, and comparisons of search and sort algorithms.
Core constructs
Every algorithm is built from sequence, selection and iteration. Definite loops run a known number of times; indefinite loops depend on a condition and must change something inside the body or they never terminate. Arrays store same-type elements under one identifier and are indexed; records group named fields of different types. Scope determines where an identifier is visible, so a local variable declared in a subprogram is not accessible outside it.
Parameters and efficiency
Pass by value copies the argument, so changes are lost on return; pass by reference passes the address, so the subprogram can modify the caller's variable. Binary search is O(log n) but only works on sorted data; linear search is O(n) and works on any order. Bubble, selection and insertion sort are O(n squared) in the average and worst cases.
Worked example
Binary search for 23 in the sorted list [3, 8, 12, 19, 23, 31, 40], using 1-based indices.
low = 1, high = 7, mid = 4, value 19 < 23, so low = 5. low = 5, high = 7, mid = 6, value 31 > 23, so high = 5. low = 5, high = 5, mid = 5, value 23 found. Three comparisons.
Each step halves the remaining search space, which is why the cost grows logarithmically rather than linearly.
Traps
- Writing a loop that never updates its control variable.
- Testing binary search on unsorted data.
- Confusing pass by value with pass by reference.
- Forgetting to initialise a running total to 0 or a product to 1.
- Trace tables that skip the final failed condition check.