22.3.1. Base Case Optimality

Try these first

1. 1.

   What is the main purpose of Huffman coding?

   Hint

   Remember why we want to encode data.

2. 2.

   Define what is meant by 'base case' in a recursive algorithm.

   Hint

   Think about what ends the recursive calls.

3. 3.

   What is the main aim of Huffman coding?

   • Data encryption
   • Data compression
   • Data transmission

   Hint

   Think about what happens when we compress files.

4. 4.

   True or False: Huffman's algorithm guarantees a globally optimal solution.

   • True
   • False

   Hint

   Reflect on how the process specifically ranks frequency.

5. 5.

   Given a set of letters with the following frequencies: T=0.05, E=0.2, S=0.1, A=0.3, N=0.15, how would you construct the Huffman tree? Show all workings.

   Hint

   Maintain a log of steps, ensuring you always merge the lowest two.

6. 6.

   Discuss the implications of different character frequency distributions on the optimality of Huffman coding. What scenarios would lead to less optimal encodings?

   Hint

   Think about how the nature of inputs changes the efficiency of the merging process.