22.6.1. Shannon and Fano's Contributions

Try these first

1. 1.

   What is the primary goal of Shannon and Fano's contributions to information theory?

   Hint

   Think about how information is processed and transmitted.

2. 2.

   Define optimal encoding in your own words.

   Hint

   Consider what makes encoding efficient.

3. 3.

   What is the main strategy employed by Shannon and Fano in encoding?

   • Using random frequencies
   • Merging the highest frequencies
   • Merging the lowest frequencies

   Hint

   Focus on how optimal coding is achieved.

4. 4.

   Huffman coding is considered a greedy algorithm. True or False?

   • True
   • False

   Hint

   Consider the characteristics of greedy algorithms.

5. 5.

   Given characters A, B, C, and D with frequencies 0.4, 0.3, 0.2, and 0.1 respectively, demonstrate how to create a Huffman tree and identify the encoding for each character.

   Hint

   Visualize the character frequencies and how they merge to form the tree structure.

6. 6.

   Prove that merging the two smallest frequencies is optimal by providing a counter example where merging does not lead to the optimal average length.

   Hint

   Analyze encoding lengths for different configurations.