GATE 2021 CS (CS2) – Question 36
Assign a binary prefix code to each letter of abbccdddee. For letters with equal frequencies, a letter earlier in dictionary order must have code length no greater than a later letter. Find the minimum encoded-string length.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) 23
Explanation
The frequencies of a,b,c,d,e are 1,2,2,3,2. Huffman merging combines 1+2=3, 2+2=4, 3+3=6, then 4+6=10. The merge-weight sum is 3+4+6+10=23, the optimal encoded length. Equal-frequency codes can be assigned lengths b=2,c=2,e=3 to meet the alphabetic length condition, with a=3,d=2. Thus B.