Examinable Syllabus for Algorithms II

Algorithms II (25/26, Easter Term) — Complete Topic List

The Algorithms II syllabus follows CLRS (3rd edition) chapters 20-26, 33, plus Sections 3 and 4 from the 25/26 lecture notes by Dr John Fawcett. The Tripos paper for Algs II is Paper 1 Questions 9 and 10 (and potentially p2q7-8, p3q7-8, p4q7-8 under the 2024 restructuring). Past papers are available from 2022-2026.

Section 1: Graphs and Path-Finding Algorithms

Graph Fundamentals

• Representations: adjacency lists vs adjacency matrices; space/time tradeoffs
• Terminology: directed/undirected, weighted/unweighted, connected components, transpose graph, in-degree/out-degree, induced subgraphs, cliques, complement graph, acyclic graphs

Breadth-First Search (BFS)

• Queue-based traversal, $O(V+E)$
• Single-source shortest paths in unweighted graphs (hop count)
• BFS tree / predecessor subgraph
• 2-vertex colourability of a connected undirected graph
• Correctness proof: Lemma 1 (upper bound), Lemma 2 (queue ordering property $\phi$), contradiction argument

Depth-First Search (DFS)

• Stack/recursive traversal, $O(V+E)$
• Discovery time and finish time per vertex
• Edge classification: tree edges, back edges (indicates cycle), forward edges, cross edges
• Properties linking discovery/finish intervals
• Topological sort: sort vertices by descending finish time on a DAG

Strongly Connected Components (SCC)

• Kosaraju’s algorithm: DFS on $G$, compute $G^T$, DFS on $G^T$ in descending finish order
• Output: each DFS tree in $G^T$ is an SCC

Single-Source Shortest Paths (SSSP)

• Bellman-Ford: handles negative edges, detects negative cycles (relaxation on $V$-th pass). $O(VE)$.
• DAG SSSP: topological sort + relaxation, $\Theta(V+E)$
• Dijkstra: non-negative weights only. Greedy + priority queue. $O((V+E)\log V)$ with binary heap.
  • Correctness proof: convergence property of relax, induction on $S$.
• Complications: negative cycles, zero-weight cycles

All-Pairs Shortest Paths (APSP)

• Floyd-Warshall (DP): $O(V^3)$. $d_{ij}^{(k)} = \min(d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)})$.
• Johnson’s algorithm: reweighting via Bellman-Ford + $V$ Dijkstra runs. $O(V^2 \log V + VE)$. Best for sparse graphs.

Section 2: Subgraphs and Flow

Minimum Spanning Trees (MST)

• Safe Edge Theorem: an edge is safe if it is a light edge crossing a cut that respects the current edge set
• Kruskal: sort edges, use disjoint sets. $O(E \log V)$.
• Prim: similar to Dijkstra; $O(E \log V)$ with binary heap, $O(E + V \log V)$ with Fibonacci heap.

Flow Networks

• Ford-Fulkerson: augmenting paths, residual network $G_f$. $O(E |f^*|)$.
• Edmonds-Karp: FF with BFS (shortest augmenting paths). $O(VE^2)$.
• Max-Flow Min-Cut Theorem: value of max flow = capacity of min cut.
• Bipartite matchings: reduction to max flow; Hopcroft-Karp as optimisation.

Section 3: Advanced Data Structures

Amortised Analysis

Three methods: aggregate analysis, accounting method, potential method. $\Phi(D)$ maps data structure states to non-negative reals; amortised cost $\hat{c}_i = c_i + \Delta\Phi$.

Binomial Heaps

• Mergeable priority queue ADT: Create, Insert, Peek-Min, Extract-Min, Merge, Decrease-Key, Delete, Count
• Binomial trees $B_k$: recursive definition, $2^k$ nodes, height $k$, $\binom{k}{i}$ nodes at depth $i$
• Max degree of any node $\le \lfloor \lg n \rfloor$
• Operations all $O(\lg n)$ except Create $\Theta(1)$

Fibonacci Heaps

• Same mergeable PQ ADT; improved amortised bounds
• Structure: collection of min-heap-ordered trees; circular doubly linked root and child lists; nodes have 8 fields including marked bit
• Operations and amortised costs: Insert $O(1)$, Destructive-Union $O(1)$, Extract-Min $O(\lg n)$, Decrease-Key $O(1)$
• Potential function: $\Phi = r + 2m$ (roots + 2 × marked nodes)
• Cascading cut and marking rules; grandchild rule leading to Fibonacci number bound
• Degree bound: $D(n) \le \lfloor \log_\phi n \rfloor$ where $\phi = (1+\sqrt{5})/2$
• Dijkstra speedup: $O(V \lg V + E)$ vs $O((V+E)\lg V)$ with binary heap

Disjoint Sets

• ADT: MakeSet, Find (In-Same-Set), Union
• Linked-list implementations: flat forest (weighted-union), cyclic DLL, hash table
• Forest representation with union by rank and path compression
• Complexity: $O(m \cdot \alpha(n))$ where $\alpha$ is the inverse Ackermann function
• $\alpha(n) \le 4$ for all practical $n$
• Application: Kruskal’s MST

Section 4: Geometric Algorithms (NEW 25/26)

Polygons

• Planar, closed, simple polygons; convex, star-shaped, monotone
• Shoelace formula for signed area
• Inside/outside definitions

Point-in-Polygon

• Ray casting: shoot semi-line, count edge crossings (odd = inside)
• Winding numbers: sum of signed angles; no trig implementation via cross/dot products
• Handling degenerate cases (ray through vertex)

Line Segments and Cross Products

• Cross product of 2D vectors: $a_x b_y - a_y b_x$
• Sign interpretation (CCW/CW/collinear)
• Orientation test for three points
• Convex combinations of endpoints
• Numerical advantages (no division, no trig, exact for integers)

Line Segment Intersection

• Two-segment test: straddle condition via 4 cross products
• $n$-segment sweep-line algorithm: $O((n+k)\log n)$
• Event queue + sweep-line status BST

Convex Hull

• Lower bound $\Omega(n \log n)$ by reduction from sorting
• Graham’s Scan: $\Theta(n \log n)$, sort by polar angle, stack with left-turn check
• Jarvis’s March: $\Theta(nh)$ output-sensitive, gift wrapping
• Cross products for all comparisons, no trigonometry

Summary

Section	Key Topics	Tripos Q
Graphs & Path-Finding	BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson, SCC	P1 Q9-10
Subgraphs & Flow	MST (Kruskal, Prim), Ford-Fulkerson, Edmonds-Karp, Max-Flow Min-Cut	P1 Q9-10
Advanced DS	Amortised analysis, binomial heaps, Fibonacci heaps, disjoint sets	P1 Q9-10
Geometry	Polygons, cross products, segment intersection, convex hull	P1 Q9-10