1. Harry Potter is writing a secret message to Hermione and wants to prevent it from being understood by Voldemort. He decides to use Huffman encoding to encode the message. Magically, the symbol frequencies of the message are given by generalized Fibonacci numbers, a famous sequence of integers known since antiquity. The nth generalized Fibonacci number is defined by FF-F-2 for n 1 with base cases F0 = 3 and F-4. (a) (5 pts) For an alphabet of = {a,b,c,d,e, f, g, h} with frequencies given by the first |2I non-zero generalized Fibonacci numbers, give an optimal Huffman code and the corresponding encoding tree for Harry to use. (b) (15 pts) Generalize your answer to (la) and give the structure of an optimal code when there are n letters, with the frequencies being the first n non-zero generalized Fibonacci answer iS Correct. numbers. Prove your