Project ForgeAlgorithms
Dynamic Programming & Greedy Algorithms
GATE 2007
Hard
Suppose the letters a,b,c,d,e,f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32, respectively. Which of the following is the Huffman code for the letters a,b,c,d,e,f?
- 0, 10, 110, 1110, 11110, 11111
- B11, 10, 011, 010, 001, 000
- C11, 10, 01, 001, 0001, 0000
- D110, 100, 010, 000, 001, 111
Explanation
Since each probability is exactly half the sum of the remaining ones, Huffman's greedy merge produces a 'comb'-shaped tree: a gets the shortest code (length 1), and each subsequent letter's code is one bit longer, with the two least likely letters (e,f) sharing the same length. This gives codes 0, 10, 110, 1110, 11110, 11111.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.