Question $2$

Consider the following binary sequence $($read left to right$)$:

yxyyxxxxyxyyxxyyxxxyyyxxxyyyxyxy$$xxyxxx

$($a$)$ Compress the sequence above using the Lempel$-$Ziv algorithm.

$(10$ marks$)$

$($b$)$ Calculate the probabilities of the third extension of $\{$x$,$ y$)$ in the given sequence.

$($c$)$ Calculate the entropy of the third extension of the alphabet.

$(2$ marks$)$

$(3$ marks$)$

$($d$)$ Implement Huffman coding based on the third extension of the alphabet. Give your answer as the compressed sequence in terms of x and y$.$

$(11$ marks$)[$Total Marks $26]$