Question

What is an optimal Huffman code for the following set of frequencies, based on the first 8 Fibonacci numbers?a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21a. Provide code tableb. Use the Huffman algorithm to build the treec. Generalize your answer to find the optimal code when the frequencies are the first n Fibonacci numbers.

Answer 1

Answer:

Check the explanation

Explanation:

a) kindly check the below diagram for solutions to question a

b) The Huffman algorithm used to build the tree is as follows;

• Collect n initial Huffman trees, such that each is a single leaf node Create a priority queue and insert the n trees in the priority queue for frequency

• Now, pick the two nodes having the lowest queue, and join them to form the tree such that the root of the tree has two nodes. The weight of the tree is the sum of the weight of the two data nodes

• insert the new tree in the priority queue

• Repeat the above steps until all the nodes have been combined into one tree

c) kindly check the below image for solutions to question c