In class, we learned Huffman Code. It is used to encode a set of characters using binary code $(0$ and $1)$ to minimize the total length of codes. In this problem, let's practice to use Huffman Code.

$1.(0\mathrm{.}3$pts$)$ Huffman Code is a type of prefix code. Can you briefly explain the concept, and what is the benefit of using prefix code?

$2.(0\mathrm{.}7$ pts $)$ Given a word forretress $\backslash (\{\}^\{1\}\backslash ),$ can you encode this word using Huffman Code? What is the total length of the code? Show your work.

$3.(0\mathrm{.}5$pts$)$ Is your codeword the only valid Huffman code of the word? If not, please also give another valid encoding of word forretress, which is different from the one you showed in $2.$

$4.($Bonus$,0\mathrm{.}4$ pts $)$ As you can see, Huffman Code is not unique. In fact, Yan prefers $1$ more than $0.$ He is wondering if you can design an algorithm that generates the Huffman Code and makes $1$ appears the most frequently in total. In this case, how many $1$ s and $0$ s do we have in the code for forretress? $($Note: the code should still be a Huffman code following the algorithm, instead of an arbitrary prefix code.$)$

$5.($Bonus$,0\mathrm{.}6$ pts and $1$ candy$)$ Prove the optimality of your algorithm. Namely, it does generate the Huffman Code with the most possible $1$s$.$ You can only get the bonus points and candy for this question when the algorithm in the previous question is correct.