21. Greedy Algorithms: Huffman Codes

Try these first

1. 1.

   What is the main purpose of Huffman coding?

   Hint

   Think about how encoding methods can affect data size.

2. 2.

   Define what a prefix code is.

   Hint

   Consider why it is important for decoding clarity.

3. 3.

   What does Huffman coding aim to achieve?

   • Minimize data size
   • Maximize data size
   • Standardize encoding

   Hint

   Consider how encoding affects transmission efficiency.

4. 4.

   True or False: In Huffman coding, each code can serve as a prefix for another code.

   • True
   • False

   Hint

   Remember why unique decoding is crucial.

5. 5.

   Given the character frequencies: A=0.5, B=0.25, C=0.15, D=0.1, construct a Huffman tree and derive the binary codes for each character.

   Hint

   Remember to always combine the least frequent characters.

6. 6.

   Explain how changing the frequency of characters affects the average bits per letter in a Huffman encoding scheme.

   Hint

   Consider how the principle of shorter codes for frequent letters applies.