GATE 2017 CS (CS2) – Question 60
Characters P,Q,R,S,T have probabilities 0.22,0.34,0.17,0.19,0.08. A 100-character message is Huffman encoded. Find its expected encoded length in bits.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 225.0 to 225.0
Explanation
Merge the smallest weights: 0.08+0.17=0.25, then 0.19+0.22=0.41, then 0.25+0.34=0.59, then 0.41+0.59=1. The mean code length equals the sum of merge weights, 0.25+0.41+0.59+1=2.25 bits/character. For 100 characters, expected length is 225 bits.