Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 11K / a / Solution

Huffman's algorithm repeatedly merges the two least probable current symbols, labels the two new edges $0,1$, and replaces the pair by a compound symbol whose probability is their sum. Reading paths from the final root gives a prefix code.

For optimality, first observe that in some optimal full binary tree the two least probable symbols are sibling leaves at maximum depth: exchange them with any deepest sibling pair, putting the smaller probabilities at no smaller depths, without increasing expected length. Contract that sibling pair to one symbol of combined probability. The original expected length equals the contracted tree's expected length plus the pair's combined probability. Induction on the alphabet size now proves that choosing the two least probabilities and recursing is optimal, which is precisely Huffman's algorithm.

If a symbol has length one, it must be $a_1$. At the three-weight stage, the other two weights $x,y$ must be merged while $p_1$ survives, so $x,y\le p_1$. Thus $1-p_1=x+y\le 2p_1$, proving $p_1\ge 1/3$. Therefore $p_1<1/3$ forces every length to be at least two.

For the other bound, suppose $p_1$ is first merged at the three-weight stage, with weights $p_1,q,r$, where $q\le p_1\le r$. The preceding merge created $r=x+y$ from two weights no larger than the surviving $q$, so $r\le 2q$. Since also $r\ge p_1$, we have $q\ge p_1/2$, and henceThus this can happen only when $p_1\le 2/5$. If $p_1>2/5$, it survives until the final merge and receives a length-one word. At equality, ties can support either tree shape.

For code (a), takeHuffman merging produces lengths $(1,2,3,3)$ and expected length $2$.

Solved by gpt-5.6-sol high.