Unit 3: Algorithm Design, Data Structures and Correctness
Core concepts
Unit 3 is about designing algorithms deliberately and arguing that they are correct. You must be fluent in algorithmic specifications: given preconditions, inputs, outputs and postconditions. Know the difference between a specification (what must be true) and an implementation (how it is achieved). Be able to write and trace pseudocode with clear indentation, and to identify the primitive operations that dominate running time.
You must understand data structures and their trade-offs: arrays and lists (indexed access versus insertion cost), stacks and queues, dictionaries/hash tables, trees (binary search trees, heaps) and graphs represented as adjacency lists or adjacency matrices. For each, know the cost of search, insert and delete in the typical and worst case, and be able to choose one to fit a problem.
Correctness is examined through preconditions, postconditions, loop invariants and termination. A loop invariant must be true before the loop, maintained by each iteration, and combined with the exit condition to establish the postcondition. Proof by induction on input size is the standard tool for recursive algorithms.
Traps
- Confusing average-case with worst-case complexity; a hash table is not O(1) worst case.
- Stating an invariant that is merely true at the start but not maintained by the body.
- Forgetting to prove termination (a loop counter must strictly move toward the exit condition).
- Quoting a complexity without saying what n measures.
Rule of thumb
State the invariant as: "after i iterations, [property relating i to the data processed]", then check three things: initialisation, maintenance, and the exit case. If you cannot write it in one sentence, the algorithm is probably not understood.
Worked example: Linear search for key k in array A[1..n]. Invariant: after i iterations, k is not in A[1..i]. Initially i=0 and the range is empty, so true. Each iteration compares A[i+1]; if equal we return, otherwise the range extends and the invariant holds. On exit without success, i=n, so k is not in A[1..n], proving the postcondition.