Problem $4.$ Huffman Coding

We are given the following set of $7$ characters, with their relative frequencies $($last one is a space$)$:

$\{{(}^{\text{'}}{A}^{\text{'}},10),{(}^{\text{'}}{E}^{\text{'}},15),{(}^{\text{'}}{I}^{\text{'}},12),{(}^{\text{'}}{S}^{\text{'}},3),{(}^{\text{'}}{H}^{\text{'}},4),{(}^{\text{'}}{T}^{\text{'}},13),{(}^{\text{'}}-{?}^{\text{'}},1)\}$

a$)$ Showing all the steps, build the tree for the Huffman codes of these characters. Show the resulting binary encodings for each character after you are done.

Note: whenever you combine two trees into one, put the one with the smaller character at leftmost leaf on the left, using the following order for the characters:

This is not necessary for the correctness of you Huffman Tree, but it will insure that you will decode the string in part $($c$)$ correctly. This emphasizes the importance of using the same tree for both encoding and decoding.

b$)$ Using your tree, compute the binary code for the following string: "THIS IS A TEST"

c$)$ Using your tree, decode the following bit string:

$0011110111110001111110110011111011011110111011001$

d$)$ What are the average encoding lengths $($bits per character$)$ in the two strings above?

e$)$ The problem with the strings in $($b$)$ and $($c$)$ is that the letters do not have the same distribution $($relative frequencies$)$ as stated in $($a$).$ If we instead had a string of length $58($about one line of text$)$ with the same relative frequencies of as stated in $($a$),$ what would be the length of the encoding and how many bits per character? What if this string was of length $2900($about one page of text$)$ instead of $58--$ what would be the length of the encoding and how many bits per character?