Words like Run! Help! and Fire! are short, not because they are frequently used, but

perhaps because time is precious in the situations in which these words are required.

Suppose that S $=$ i with probability pi

$,$ i $=1,2,...,$ m$.$ Let li be the number of binary

symbols in the codeword associated with S $=$ i$,$ and let ci denote the cost per letter of the

codeword when S $=$ i$.$ Thus the average cost C of the description of S is C $=$

Pm

i$=1$ pici

li

$.$

$1$

$($a$)$ Minimize C over all l$1,$ l$2,...,$ lm such that P$2$

$$li $<=1.$ Ignore any implied integer

constraints on li

$.$ Exhibit the minimizing l

$$

$1$

$,$ l$$

$2$

$,...,$ l$$

m and the associated minimum

value C

$$

$.$

$($b$)$ How would you use the Huffman code procedure to minimize C over all uniquely

decodable codes? Let CHuffman denote this minimum.

$($c$)$ Can you show that