Examinable Syllabus for Algorithms I

Algorithms I Syllabus (25/26, Lent Term)

The following topics are examinable for the Algorithms I component of CST Paper 1 (one question from a choice of two). The course covers 12 lectures taught by Dr John Fawcett.

Sorting Algorithms

All of the following sorting methods are examinable, including pseudocode, correctness proofs (via loop invariants), and asymptotic analysis:

• Insertion sort: incremental, $\Theta(n^2)$ worst case, $\Theta(n)$ best case (sorted input). Stable, in-place. Tight loop makes it fast for small $n$.
• Merge sort: divide and conquer, $\Theta(n \log n)$ worst and average case. Stable. Not in-place (requires $\Theta(n)$ auxiliary space). Solved via Master Theorem or substitution.
• Quicksort: divide and conquer with partition about a pivot. $\Theta(n^2)$ worst case (sorted input, or constant split-off), $\Theta(n \log n)$ expected case. In-place (Lomuto or Hoare partition). Instability of partition step makes it unstable.
• Quicksort with Median-of-Medians: guarantees $\Theta(n \log n)$ worst case by selecting the median as pivot in $\Theta(n)$ time.
• Heapsort: build a max-heap in $\Theta(n)$, then extract $n-1$ times at $O(\log n)$ each. $\Theta(n \log n)$ total. In-place, unstable. Demonstrates the heap data structure.
• Counting sort: $\Theta(k + n)$, where keys are in $[0, k]$. Non-comparison; stable. Requires $k = O(n)$ to be linear.
• Radix sort: sort digit-by-digit using a stable sort (e.g. counting sort) on each digit. $\Theta(d(n + k))$ for $d$-digit numbers.
• Bucket sort: assumes uniform distribution over $[0, 1)$. $\Theta(n)$ average, $\Theta(n^2)$ worst.

Sorting lower bounds: any comparison-based sort requires $\Omega(n \log n)$ comparisons. This is an information-theoretic lower bound (decision tree argument).

Asymptotic Notation

All five notations must be understood, with formal definitions and the ability to prove membership:

Notation	Meaning	Formal definition
$O(g(n))$	Asymptotic upper bound	$0 \le f(n) \le c \cdot g(n)$ for $n \ge n_0$
$\Omega(g(n))$	Asymptotic lower bound	$0 \le c \cdot g(n) \le f(n)$ for $n \ge n_0$
$\Theta(g(n))$	Asymptotically tight bound	$c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$
$o(g(n))$	Non-tight upper bound	For any $c > 0$, $0 \le f(n) < c \cdot g(n)$
$\omega(g(n))$	Non-tight lower bound	For any $c > 0$, $0 \le c \cdot g(n) < f(n)$

Properties: transitivity (all five), reflexivity ($O, \Omega, \Theta$), symmetry ($\Theta$ only).

Algorithm Design Strategies

• Incremental: build solution step by step (insertion sort).
• Divide and conquer: split into non-overlapping subproblems, solve recursively, combine (merge sort, quicksort, quicksort MoM, quickselect, Strassen’s algorithm).
• Dynamic programming: overlapping subproblems with optimal substructure; memoisation; top-down (recursion + cache) and bottom-up (table filling).
• Greedy algorithms: locally optimal choice leads to globally optimal solution; requires proof of correctness (exchange argument).
• Semi-structures: heaps are cheaper to build than fully-sorted structures.

Methods for Solving Recurrences

• Guess and verify (substitution method): guess a bound, prove by induction.
• Substitute and spot pattern: expand recurrence, identify arithmetic/geometric series, solve closed form.
• Recursion tree method: draw call tree, sum costs per level, multiply by number of levels.
• Master Theorem: for recurrences of form $T(n) = aT(n/b) + f(n)$. Three cases based on comparing $f(n)$ with $n^{\log_b a}$.

Data Structures (Algorithms I Only)

Elementary Structures

• Pointers, NIL, objects.
• Stacks (LIFO): PUSH, POP, O(1). Array and linked-list implementations.
• Queues (FIFO): ENQUEUE, DEQUEUE, O(1). Circular buffer array implementation.
• Singly and doubly linked lists; cyclic variants; sentinel nodes.
• Rooted trees: with/without parent pointers, fixed/variable child counts.

Binary Search Trees

• BST property; SEARCH, INSERT, DELETE, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR.
• All $\Theta(h)$; $h = \Theta(n)$ worst case, $\Theta(\log n)$ expected for random insertion.
• Inorder traversal produces sorted order.

Balanced Search Trees

• B-trees: minimum degree $t$; $t-1$ to $2t-1$ keys per node; $t$ to $2t$ children. Height $\le \log_t((n+1)/2)$. Search, insert (top-down splitting), delete (redistribute/merge). All $O(\log n)$. Disk I/O motivation.
• 2-3-4 trees: B-tree with $t=2$. 1—3 keys, 2—4 children per node. Conceptual bridge to red-black trees.
• Red-black trees: five colour properties, black-height, height $\le 2\log(n+1)$. Insertion fix-up (3 cases: recolour, zig-zag rotation, zig-zig rotation). Isomorphism with 2-3-4 trees. All operations $O(\log n)$.

Hash Tables

• Dictionary ADT: INSERT, DELETE, SEARCH.
• Hash functions: division method, multiplication method, range reduction.
• Collision resolution by chaining (4 variants).
• Collision resolution by open addressing (linear, quadratic, double hashing).
• Primary and secondary clustering.
• Load factor $\alpha = n/m$, resizing, amortised $\Theta(1)$ insert.
• Universal hashing: definition, example family, adversarial protection.

Priority Queues and Heaps

• Binary heaps: min-heap and max-heap. Structural property (complete tree) and ordering property (parent $\le$ children for min-heap).
• Array representation: root at index 1, children at $2i$ and $2i+1$, parent at $\lfloor i/2 \rfloor$.
• MAX-HEAPIFY (REHEAPIFY): $O(\log n)$.
• BUILD-MAX-HEAP: $\Theta(n)$.
• HEAPSORT: $\Theta(n \log n)$.
• Priority queue operations: INSERT, EXTRACT-MIN/MAX, DECREASE-KEY, all $O(\log n)$ via heap; also implementable via red-black trees.

Order Statistics

• MINIMUM and MAXIMUM in $\Theta(n)$ via linear scan; simultaneous min+max in $\le 3\lfloor n/2 \rfloor$ comparisons.
• Quickselect: expected $\Theta(n)$, worst case $\Theta(n^2)$. With Median-of-Medians: worst case $\Theta(n)$.

Tripos Question Format

Algorithms I is assessed in CST Paper 1, questions 7 and 8 (one to be answered from two). Typical structure:

• Part (a): theory, definition, proof (e.g. state a loop invariant, prove correctness, derive a height bound).
• Parts (b—d): application, algorithm design, tracing, or modifying an algorithm for a variant problem.

Past papers from 2006—2026 are available. The syllabus is broadly stable across years.

Summary of Examinable Topics

Category	Topics
Sorting	Insertion, Merge, Quick, Heap, Counting, Radix, Bucket; stability; lower bounds
Asymptotics	$O$, $\Omega$, $\Theta$, $o$, $\omega$; definitions and properties
Recurrences	Substitution, tree method, Master Theorem
Design strategies	Incremental, divide and conquer, DP, greedy, semi-structures
Proofs	Loop invariants (initialisation, maintenance, termination); induction
Elementary DS	Stacks, queues, linked lists, trees
BSTs	Search, insert, delete; degeneracy
Balanced trees	B-trees, 2-3-4 trees, red-black trees; isomorphism
Hash tables	Chaining, open addressing, universal hashing, resizing
Heaps	Heapify, heapsort, priority queues
Order statistics	Quickselect, Median-of-Medians