22.5. Greedy Algorithm Nature of Huffman's Approach

Try these first

1. 1.

   What does Huffman's algorithm aim to achieve?

   Hint

   Think about what makes an algorithm 'optimal'.

2. 2.

   Why is two the base case for Huffman's algorithm?

   Hint

   Consider the simplest case of assigning binary values.

3. 3.

   What is the primary strategy used in Huffman's algorithm?

   • Maximize frequencies
   • Merge lowest frequencies
   • Assign equal frequencies

   Hint

   Think about the greedy strategy!

4. 4.

   True or False: Huffman coding guarantees an optimal prefix code for given frequencies.

   • True
   • False

   Hint

   Focus on the proof we discussed!

5. 5.

   Given the frequencies of characters A=5, B=9, C=12, D=13, E=16, F=45, construct the Huffman tree and present the codes for each character.

   Hint

   Start by merging A and B, then C, D, E with the previous results.

6. 6.

   Explain how a heap could be integrated into Huffman’s algorithm to enhance its efficiency and the resultant benefits.

   Hint

   Think about how heaps allow efficient insertions and deletions.