22.1.3. Algorithm Description

Try these first

1. 1.

   What is Huffman coding used for?

   Hint

   Think about how files are made smaller for easier transmission.

2. 2.

   Define a greedy algorithm.

   Hint

   Consider choices that seem optimal immediately.

3. 3.

   What is the main purpose of Huffman's algorithm?

   • To create a binary tree
   • To encode letters optimally
   • To decode files

   Hint

   Focus on what Huffman is trying to achieve.

4. 4.

   True or False: The greedy algorithm always produces optimal results.

   • True
   • False

   Hint

   Consider the implications of greedy methods.

5. 5.

   Using the letters A, B, C, and D with frequencies 10, 15, 30, and 45 respectively, draw the Huffman tree and provide the bit encoding for each letter.

   Hint

   Keep merging the two smallest frequencies until you reach one tree.

6. 6.

   Assuming you have the letters E, F, G with frequencies 12, 5, 8, explain why merging E and F first is a suboptimal choice in an imagined scenario with a higher frequency letter.

   Hint

   Analyze how splitting larger frequencies affects the overall encoding.