Description
1) 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:21
Can you generalize your answer to find the optimal code when the frequencies are the first n
Fibonacci numbers? [CLRS 16.3-3]
(15 points)
2) Generalize Huffman’s algorithm to ternary codewords (i.e., codewords using the symbols 0, 1,
and 2), and write down the corresponding pseudo-code using priority queue. [Partially CLRS
16.3-7]
(20 points)
3) Use Dijkstra shortest path algorithm to determine shortest paths from S to other nodes in the
following graph. Show all the steps in a table.
(15 points)
