22.1. Introduction to Recursive Solutions and Huffman Coding

Try these first

1. 1.

   What happens when you merge two letters in Huffman coding?

   Hint

   Think about how you combine two values.

2. 2.

   Why is it important to use lower frequency letters in Huffman coding?

   Hint

   Consider the need for compression.

3. 3.

   What is the first step in constructing a Huffman tree?

   • Combine the highest frequencies
   • Merge two lowest frequencies
   • Assign codes to letters

   Hint

   Think about how frequencies are organized.

4. 4.

   True or False: Huffman coding guarantees the shortest possible encoding for any set of frequencies.

   • True
   • False

   Hint

   Consider how merging impacts encoding.

5. 5.

   You are given frequencies of 0.12, 0.20, 0.23, 0.15, and 0.30. Construct the Huffman tree and provide the process.

   Hint

   Combine the smallest pairs first, progressing iteratively.

6. 6.

   Explain why a greedy approach is suitable for Huffman coding. Provide an example of how it works.

   Hint

   Think about local versus global optimal choices.