22.5.1. Locally Optimal Choices

Try these first

1. 1.

   What is Huffman coding?

   Hint

   Think about how it deals with letter frequencies.

2. 2.

   Define a composite node in Huffman coding.

   Hint

   Focus on the merging process.

3. 3.

   What is the basis of making local optimal choices in Huffman coding?

   • Merging the highest frequencies
   • Merging the lowest frequencies
   • Ignoring frequencies

   Hint

   Consider the purpose of letter frequency in encoding.

4. 4.

   Huffman coding is considered a greedy algorithm. True or False?

   • True
   • False

   Hint

   Think about how decisions are made with no going back.

5. 5.

   Given the following frequencies: A: 0.3, B: 0.1, C: 0.2, D: 0.4, construct the Huffman tree and determine the corresponding binary codes.

   Hint

   Track merges carefully, assigning 0 and 1 to child nodes to create codes.

6. 6.

   Explain the flaws of using a naive greedy algorithm in constructing a tree. Consider at least two alternative combinations and their outcomes.

   Hint

   Think about the implications of higher frequency letters during tree construction.