Voldemort is writing a secret message to his lieutenants and wants to prevent it from being understood by mere Muggles. He decides to use Huffman encoding to encode the message. Magically, the symbol frequencies of the message are given by the Lucas numbers, a famous sequence of integers discovered by the same person who discovered the Fibonacci numbers. The nth Lucas number is defined as Ln = Ln1 + Ln2 for n > 1 with base cases L0 = 2 and L1 = 1.

(a) For an alphabet of = {a, b, c, d, e, f, g, h} with frequencies given by the first || Lucas numbers, give an optimal Huffman code and the corresponding encoding tree for Voldemort to use.

(b) Generalize your answer to (3a) and give the structure of an optimal code when the frequencies are the first n Lucas numbers.