Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 3I / b / Solution

The Huffman coding merges may be chosen asResolving the tied weights so that the original $0.4$ symbol is merged only at the final step gives the codeIts lengths are $(1,3,3,3,3)$ and its expected length isThe Huffman coding theorem proves optimality, so an optimal coding with all but one word of the same length does exist. This is an instance of a nonunique optimal prefix code: a different resolution of the ties also gives the optimal profile $(2,2,2,3,3)$.

An optimal code cannot have five distinct lengths. By the deepest sibling property of an optimal prefix code, at least two maximal-length codewords have the same length. Thus the answers are respectively