(a) Briefly describe the methods of Shannon-Fano and of Huffman for the construction of prefix-free binary codes.

(b) In this part you are given that $-\log _{2}(1 / 10) \approx 3.32,-\log _{2}(2 / 10) \approx 2.32$, $-\log _{2}(3 / 10) \approx 1.74$ and $-\log _{2}(4 / 10) \approx 1.32$.

Let $\mathcal{A}=\{1,2,3,4\}$. For $k \in \mathcal{A}$, suppose that the probability of choosing $k$ is $k / 10$.

(i) Find a Shannon-Fano code for this system and the expected word length.

(ii) Find a Huffman code for this system and the expected word length.

(iii) Verify that Shannon's noiseless coding theorem is satisfied in each case.