Algorithm design and problem solving
Algorithm design and problem solving tests how you decompose a problem, express a solution in pseudocode or a flowchart, hand-trace it, and choose an appropriate standard algorithm. Marks come from precision: initialisation, loop bounds and termination.
Design tools
Decomposition breaks a problem into sub-problems; abstraction removes detail irrelevant to the current level. Before coding, identify inputs, processes, outputs and preconditions. Pseudocode uses sequence, selection (IF, CASE) and iteration (FOR, WHILE, REPEAT). Validation checks that data is reasonable; verification checks that it has not changed between input and storage.
Standard algorithms
A linear search checks each item in turn, works on unsorted data and is O(n). A binary search repeatedly halves a sorted list and is O(log n). A bubble sort compares adjacent pairs and swaps, with a pass ending when no swaps occur; it is easy to write but O(n²). Insertion sort builds a sorted section one item at a time and performs well on nearly sorted data. Recursion needs a base case; every call adds a stack frame, so deep recursion can overflow.
Worked example
Search for 43 in [12, 19, 24, 31, 38, 43, 56, 62, 71, 80]. low = 1, high = 10, so mid = 5, value 38. Since 43 > 38, low becomes 6. mid = (6 + 10) DIV 2 = 8, value 62; since 43 < 62, high becomes 7. mid = (6 + 7) DIV 2 = 6, value 43: found after three comparisons. The list must be sorted, and integer division must be used.
Trace tables
Give each variable a column plus one for output. Update values in the order the program does, and check the loop condition at the correct point: a WHILE tests before the body, a REPEAT tests after.
Traps
Using binary search on unsorted data; forgetting to reset a flag or counter each pass; off-by-one errors in high and low; omitting a recursion base case; confusing validation with verification.