1. Show that a Huffman tree can be constructed in linear time if the alphabet symbols are given in a sorted order of their frequencies.
2. Given a Huffman coding tree, which algorithm would you use to get the codewords for all the symbols? What is its time-efficiency class as a function of the alphabet size?
3. Explain how one can generate a Huffman code without an explicit generation of a Huffman coding tree.