22.3. Proof of Optimality

Try these first

1. 1.

   What is Huffman coding?

   Hint

   Think about the role of character frequency in creating codes.

2. 2.

   Why are prefix codes important?

   Hint

   What would happen if two codes began the same way?

3. 3.

   What does Huffman's algorithm aim to achieve?

   • Maximal coding length
   • Optimal coding based on frequency
   • Random coding

   Hint

   Recall the goal behind character encoding.

4. 4.

   True or False: Huffman coding uses a greedy approach.

   • True
   • False

   Hint

   Consider how the algorithm chooses elements.

5. 5.

   Design a Huffman tree for the frequencies A: 0.15, B: 0.25, C: 0.35, D: 0.25.

   Hint

   Keep merging the smallest nodes, tracking frequencies through each step.

6. 6.

   Using induction, explain why merging the two smallest frequencies will always yield an optimal Huffman tree.

   Hint

   Reflect on the properties of frequency distribution in your explanation.