"The binary sequence
s = 111111111000000111111111111111100001 = 1^9,0^6,1^16,0^4,1
was generated by a stationary two-state Markov chain with transition probabilities p1|0 =
2p0|1 = 0.2. Encode s using
(a.1) a Huffman code for 3-bit symbols based on the source model,
(a.2) a Huffman code for 3-bit symbols based on relative frequencies in s;
(b.1) a Shannon-Fano-Elias code or an arithmetic code for 3-bit symbols based on the source model,
(b.2) a Shannon-Fano-Elias code or an arithmetic code for 3-bit symbols based on relative frequencies in s;
(c.1) an arithmetic stream code (as described in CT or class) based on the source model,
(c.2) an adaptive arithmetic stream code (as described in class; use Prob. 2), based on s;
(d.1) the "basic" Lempel-Ziv algorithm (CT),
(d.2) the "modified" Lempel-Ziv algorithm (class).
(e) Relate your answers to the entropy rate of the Markov source and the entropy of s based on relative frequencies.
You need not solve every problem by pen and paper. The arithmetic stream codes get quickly out of hand. If you choose to write a program, please turn in your "source code" with your solution"