Describe the Huffman coding scheme and prove that Huffman codes are optimal.

Are the following statements true or false? Justify your answers.

(i) Given $m$ messages with probabilities $p_{1} \geqslant p_{2} \geqslant \cdots \geqslant p_{m}$ a Huffman coding will assign a unique set of word lengths.

(ii) An optimal code must be Huffman.

(iii) Suppose the $m$ words of a Huffman code have word lengths $s_{1}, s_{2}, \ldots, s_{m}$. Then

$$\sum_{i=1}^{m} 2^{-s_{i}}=1$$

[Throughout this question you may assume that a decipherable code with prescribed word lengths exists if and only if there is a prefix-free code with the same word lengths.]