$8$ Standard $8$: Huffman Encoding

$8\mathrm{.}1$ Problem $1$

Problem $1.$ Consider the following sequence of numbers:

$S_n=\{\begin{array}{cc}3,& n=0\\ 6,& n=1\\ S_{n-1}+(-1{)}^n**S_{n-2},& n2.\end{array}$

For an alphabet $=\{a,b,c,d,e,f,g,h,i,j\}$ with frequencies given by the first $||$ many numbers $S_0,S_1,$dots,$S_{||-1},$

give an optimal Huffman code and its corresponding encoding tree. Specify the frequencies of each letter, and

for each stage of the algorithm, the subtrees merged at that stage, and the resulting total frequency for the new

merged subtree. The Huffman encoding is constructed the following way:

$8\mathrm{.}1.$a Problem $1(a)$

$($a$)$ For each letter, state its frequency $($clearly in tabular form$)$

Answer.

$8\mathrm{.}1.$b Problem $1(b)$

$($b$)$ Steps, including individual subtree and frequencies, and priority queue

Answer.

$8\mathrm{.}1.$c Problem $1($c$)$

$($c$)$ Final Huffman tree using LaTeX

Answer.

$8\mathrm{.}1.$d Problem $1($d$)$

$($d$)$ Final Huffman code for each letter

Answer.