Tripos Question Patterns for Algorithms II

Paper Structure

Algorithms II appears on Paper 1 Questions 9 and 10 in the Part IA Tripos. Under the 2024 restructuring, it may also appear on p2q7-8, p3q7-8, p4q7-8. Past papers from 2022-2026 are directly relevant. Each question carries approximately equal marks (typically 20 marks, split into parts a-d or a-e).

Common Question Structures

Tripos questions follow predictable patterns. Most have 4-5 parts that build from definition/stating through execution to analysis or modification.

Part (a): Define, State, or Describe

Bookwork: state a theorem, define a concept, or describe a data structure. Examples:

• State the max-flow min-cut theorem.
• Define what it means for an edge to be “safe” in the context of MST algorithms.
• Define the three amortised analysis methods (aggregate, accounting, potential).
• Describe the structure of a Fibonacci heap (root list, child lists, node attributes, mark bit).
• Name the two heuristics used in the optimal disjoint-set implementation and describe each.

Strategy: Concise, precise definitions. Use mathematical notation where appropriate. One or two sentences per point.

Part (b): Trace an Algorithm on a Given Input

The most common question type. You are given a concrete graph, set of points, or sequence of operations, and must trace the algorithm step by step.

For graph algorithms (BFS, DFS, Dijkstra, Bellman-Ford, Ford-Fulkerson):

• Show a table with columns for each vertex (d, $\pi$, marked, etc.) at each iteration.
• Draw the state at key snapshots.
• For Dijkstra, show the priority queue contents after each iteration.
• For DFS, show a table of (discover_time, finish_time) for each vertex.
• For Ford-Fulkerson, draw the residual network after each augmentation.

For Fibonacci heap questions:

• Trace insert, decrease-key, extract-min on a small example.
• Show the root list and tree structure after each step.
• For extract-min, show the consolidation array and which trees merge.

For disjoint-set questions:

• Draw the trees after each Union.
• Show rank values and how they change.
• Show the effect of Find with path compression.

For geometric questions (new):

• Given a set of 8-10 points with coordinates, run Graham’s scan: show the sorted order, stack contents after each point.
• Run Jarvis’s march on the same set; show each step finding the next hull vertex.
• Test segment intersection: compute the four cross products and interpret the signs.

Strategy: Be methodical. Show all intermediate states. Use clearly labelled diagrams or tables. Even if you make an arithmetic error, the examiner can follow your working and award method marks.

Part (c): Prove Correctness or Analyse Complexity

This is the analysis component. May ask you to:

• Prove an algorithm correct (usually by induction on an invariant).
• Derive the amortised cost of an operation using the potential method.
• Analyse the running time of a given algorithm, stating which part dominates.
• Prove the degree bound in a Fibonacci heap ($D(n) \le \lfloor \log_\phi n \rfloor$).

For correctness proofs, the expected structure:

1. State the invariant clearly.
2. Initialisation: base case, show invariant holds before the loop.
3. Maintenance: assume invariant holds at the start of an iteration; show it holds after.
4. Termination: when the loop ends, the invariant implies correctness.

Example: Proving Dijkstra’s correctness uses the invariant “for all $v \in S$, $v.d = \delta(s,v)$”, plus the convergence property of relax.

For amortised analysis, the expected structure:

1. Choose/state the potential function $\Phi$.
2. Verify $\Phi$ is non-negative and $\Phi(\text{initial}) = 0$.
3. For each operation, compute $\Delta \Phi$ and $\hat{c}_i = c_i + \Delta \Phi$.
4. Sum over the sequence to bound total cost.

Part (d): Apply to a New Scenario or Modify the Algorithm

Tests deeper understanding. You might be asked to:

• Adapt an algorithm to solve a variant problem (e.g. “modify Dijkstra to return all shortest paths”).
• Compare two data structures for a given application, explaining which is better and why.
• Explain why an algorithm fails on certain inputs (e.g. “why does Dijkstra fail on negative edges?”).
• Given an $\Omega(n \log n)$ lower bound, explain why a proposed $O(n)$ algorithm must be incorrect, identifying the flaw.
• Apply a geometric algorithm to a non-standard problem (e.g. “how would you test whether two convex polygons intersect?”).

Strategy: Start from the known algorithm, identify the step that needs changing, and explain the modification. Use the same notation as the original algorithm. Analyse the running time of your modification.

Example Question Breakdown (Hypothetical)

Q9. (a) State the safe-edge theorem for minimum spanning trees. [3 marks]

Q9. (b) Run Kruskal’s algorithm on the following graph, listing the edges in the order they are added to the MST. [6 marks]

Q9. (c) Explain how a disjoint-set data structure with union-by-rank and path compression can be used in Kruskal’s algorithm. Analyse the overall running time. [5 marks]

Q9. (d) A colleague proposes using a sorted linked list as the priority queue in Dijkstra’s algorithm. Explain why this is a bad choice, and compare with a Fibonacci heap. [3 marks]

Q9. (e) Prove that the following invariant holds throughout the WHILE loop of Dijkstra’s algorithm: for all $v \in S$, $v.d = \delta(s,v)$. [3 marks]

Key Proofs to Memorise

The following proofs should be known at the level of detail demonstrated in lectures and CLRS:

Proof	Method
BFS correctness	Breakpoint proof with queue-ordering invariant
Dijkstra correctness	Induction on $S$ + convergence property of relax
Bellman-Ford correctness	Induction on number of relax passes
Max-Flow Min-Cut	Cut capacity as upper bound + construction from residual graph
Safe Edge Theorem	Cut-and-paste argument
Fibonacci heap degree bound	Grandchild lemma + Fibonacci recurrence + induction
Potential analysis of FibHeap decrease-key	Case analysis on $\Phi = r + 2m$

Practical Advice

1. Time management: Each question is ~30-35 minutes. Allocate proportional time to each part based on marks.
2. Diagrams: Draw clear, labelled diagrams. For graph algorithms, draw the graph and annotate distances. For geometric questions, plot the points.
3. Tables: Use tabular format for tracing (vertex states, queue contents, array indices).
4. Show working: Partial marks are awarded for method, even if the final answer is wrong.
5. Notation: Use the same notation as the lecture notes ($d$, $\pi$, $\delta$, $\Phi$, etc.).
6. New geometric questions: Expect them to be accessible; the first year of a new topic usually has straightforward bookwork + tracing.
7. British spelling: In written answers, use “neighbour”, “colour”, “minimise”, “optimise”, etc.

Summary

Question Part	Typical Content	Marks ~
(a)	State theorem / define concept	3-4
(b)	Trace algorithm on given input	5-7
(c)	Prove correctness / analyse complexity	5-6
(d)	Apply to new scenario / modify algorithm	3-5
(e)	Further analysis / comparison / proof	3-5