Paper 1, Section I, H

Coding and Cryptography
Part II, 2013

A binary Huffman code is used for encoding symbols 1,,m1, \ldots, m occurring with respective probabilities p1pm>0p_{1} \geqslant \cdots \geqslant p_{m}>0 where 1jmpj=1\sum_{1 \leqslant j \leqslant m} p_{j}=1. Let s1s_{1} be the length of a shortest codeword and sms_{m} the length of a longest codeword. Determine the maximal and minimal values of each of s1s_{1} and sms_{m}, and find binary trees for which they are attained.