2. (Number of Typical Sequences) Design an algorithm for calculating PX(A(X)) and the number
jA(X)j of typical binary sequences x = (x1; : : : xn) with probability PX0(0) = p, a given , and
the length of the sequences n.
Optional: (Programming needed) What are the number of -typical sequences and PX(A(X)) for
p = 1/3 ,  = 0:046 and n = 1000.

3. (HUFFMAN and SHANNON-FANO Code) Consider the random variable X = fx1; :::; x7g with
P(x1) = 0:49, P(x2) = 0:26, P(x3) = 0:12, P(x4) = 0:04, P(x5) = 0:04, P(x6) = 0:03,
P(x7) = 0:02.
a) Construct a binary HUFFMAN code for X.
b) Construct a binary SHANNON-FANO code for X.
c) Compute the expected code length for the codes.
d) Construct a ternary HUFFMAN code for X.

4. (Optimal Codeword Length) Although the codeword lengths w(x) of an optimal variable length code
are complicated functions of the message probabilities pi = PX(xi), it can be said that less probable
symbols are encoded into longer codewords. Suppose that the message probabilities are given in
decreasing order p1 > p2 


 pn.

a) Prove that for any binary HUFFMAN code, if the most probable message symbol has probability
p1 > 2/5 , then that symbol must be assigned a codeword of length 1.

b) Prove that for any binary HUFFMAN code, if the most probable message symbol has probability
p1 < 1/3 , then that symbol must be assigned a codeword of length  2.
1