Proof Strategies for Algorithms I

Why Proofs Matter in Algorithms I

The exam frequently asks for proofs: correctness of an algorithm, a height bound for a tree, optimality of a greedy choice, or tightness of an asymptotic bound. Marks are awarded for clarity, rigour, and correctly identifying the induction variable and hypothesis.

Two main proof strategies appear throughout the course: breakpoint induction (loop invariants) and along-a-path induction (used in Algorithms II but also relevant in Algorithms I for tree and heap properties).

Breakpoint Induction (Loop Invariants)

Used when an algorithm contains a loop. The invariant is a property that holds at a specific “breakpoint” — typically the start of each loop iteration.

Three-Part Structure

1. Initialisation: the invariant holds before the first iteration.
2. Maintenance: if the invariant holds at the start of an iteration, it holds at the start of the next.
3. Termination: when the loop terminates, the invariant (combined with the termination condition) proves the algorithm’s correctness.

Example: Insertion Sort Correctness

Invariant P: At the start of each iteration of the FOR loop (index $j$), the subarray $A[1..j-1]$ contains the same elements as originally in positions $1..j-1$, but in sorted order.

Initialisation ($j=2$): $A[1..1]$ is trivially sorted (one element).

Maintenance: The WHILE loop shifts larger elements right by one position, creating space for $A[j]$ at its correct sorted position within $A[1..j]$. After insertion, $A[1..j]$ is sorted. The next iteration starts with $j+1$, so $A[1..(j+1)-1] = A[1..j]$ is sorted.

Termination: When $j = n+1$, the invariant says $A[1..n]$ is sorted. This is exactly the desired output.

Example: Partition Correctness

Invariant P: At the start of each FOR loop iteration (with index $j$), for any array index $k$:

1. If $p \le k \le i$, then $A[k] \le x$ (the pivot).
2. If $i+1 \le k \le j-1$, then $A[k] > x$.
3. If $k = r$, then $A[k] = x$.

Initialisation: $i = p-1$, so no $k$ satisfies condition 1 (vacuously true); similarly condition 2 vacuous. Condition 3 holds because $x = A[r]$.

Maintenance: Case split on whether $A[j] \le x$ or $A[j] > x$. In both cases, incrementing $i$ and swapping maintains the three regions.

Termination: $j = r$, so the unprocessed region is empty. The final swap of $A[i+1]$ with $A[r]$ places the pivot correctly, satisfying the post-condition: all elements left of the pivot are $\le$ pivot, all right of pivot are $>$ pivot.

Pitfalls in Loop Invariant Proofs

1. Vague invariants: “the array is sorted so far” is too vague. Must specify which subarray, what “sorted” means, and the relationship to the original input.
2. Missing the induction variable: must specify what the induction is over (the loop counter $j$, the number of iterations, etc.).
3. Invariant that is true but useless: e.g. "$1 = 1$" holds throughout but proves nothing.
4. Forgetting the termination condition: the invariant must combine with the loop exit condition to yield correctness.

Along-a-Path Induction

Used in graph and tree algorithms where correctness propagates along a path or from root to leaves.

Structure: Prove a property $P(v)$ for vertices on a shortest path (or along a tree traversal), showing:

• Base: $P$ holds for the start vertex (or root).
• Inductive step: If $P$ holds for a vertex $u$ on the path, and the algorithm processes $u$‘s successor $v$ next, then $P$ holds for $v$ after processing.

Example (BFS shortest paths) used in Algorithms II but with relevance to Algorithms I proofs: prove that when BFS first discovers a vertex at distance $d$, the discovered path is indeed a shortest path.

Proving Height Bounds for Balanced Trees

B-Tree Height

Claim: For a B-tree with minimum degree $t$ and $n$ keys, $h \le \log_t((n+1)/2)$.

Proof: Count minimum keys per level. Root: $\ge 1$ key. Level 1: $\ge 2(t-1)$ keys (minimum $t-1$ keys in each of 2 nodes). Level 2: $\ge 2t(t-1)$ keys. Level $i$: $\ge 2t^{i-1}(t-1)$ keys. Summing the geometric series for $h+1$ levels (root through deepest internal nodes) and rearranging gives the bound.

Red-Black Tree Height

Claim: $h \le 2\log(n+1)$.

Proof: Show the subtree rooted at any node $x$ has $\ge 2^{bh(x)} - 1$ internal nodes (by induction on the subtree height). The black-height of the root $\ge h/2$ (at least half the nodes on any path are black by Property 4). Hence $n \ge 2^{h/2} - 1$, so $h \le 2\log(n+1)$.

Proving Greedy Optimality (Exchange Argument)

Structure:

1. Assume an optimal solution $S^*$ exists.
2. Show that the greedy choice can be swapped into $S^*$ without decreasing optimality.
3. By induction, iteratively transforming $S^*$ to match greedy choices yields a greedy solution that is also optimal.

Example: Activity selection (choose max number of non-overlapping activities). Greedy choice: pick activity with earliest finish time. Proof: if the optimal solution does not include the earliest-finishing activity, replacing its first activity with the earliest finisher cannot increase conflicts (the earliest finisher leaves the maximum remaining time for others).

Proving Asymptotic Bounds

From definitions: $f(n) \in O(g(n))$ means $\exists c > 0, n_0$ such that $\forall n \ge n_0, 0 \le f(n) \le c \cdot g(n)$.

Example: Show $3n^2 + 2n + 1 \in O(n^2)$. Choose $c = 6$ and $n_0 = 1$. For $n \ge 1$: $3n^2 + 2n + 1 \le 3n^2 + 2n^2 + n^2 = 6n^2 = c \cdot n^2$.

Example: Show $3n^2 + 2n + 1 \notin O(n)$. For any $c$, $3n^2 + 2n + 1 > cn$ for sufficiently large $n$ (since $n^2$ dominates). Use proof by contradiction: assume $3n^2 + 2n + 1 \le cn$ for large $n$, divide by $n$, get $3n + 2 + 1/n \le c$, which fails as $n \to \infty$.

Exam Proof Checklist

When writing a proof in the Tripos:

• State the inductive hypothesis clearly: what is $P(n)$ and what is $n$?
• Specify the induction type (ordinary, strong, over program execution).
• Cover base case(s) explicitly.
• Show the inductive step $P(k) \Rightarrow P(k+1)$ (or $P(k) \Rightarrow P(k')$ for strong induction).
• Conclude explicitly: “Therefore, the algorithm is correct” (or the bound holds).
• Avoid vague language: “clearly”, “obviously”, “it follows that” without justification.

Summary

Proof Strategy	When to Use	Example
Loop invariant (breakpoint)	Algorithm contains a loop	Insertion sort, partition, BFS
Along-a-path induction	Graph/tree traversal	BFS distances, Dijkstra (Algs II)
Induction on tree height	Balanced tree bounds	B-tree/RBT height proofs
Exchange argument	Greedy optimality	Activity selection
Asymptotic from definition	$O/\Omega/\Theta$ proofs	$3n^2 \in O(n^2)$
Induction variable	Must be explicit	$j$ (loop counter), $n$ (tree size), $d$ (distance)