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 ber is defined by F F-2 for n> 1 with base cases Fo- 3 and F1-4 (a) (5 pts) For an alphabet of = {a,b,c,d,e, f, g, h} with frequencies given by the firstnon-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 (a) and give the structure of an optimal code when there are n letters, with the frequencies being the first n non-zero generalized Fibonacci numbers. Prove your answer is correct