GATE 2023 EC – Question 65
The frequency of occurrence of 8 symbols (a-h) is shown in the table below. A symbol is chosen and it is determined by asking a series of “yes/no” questions which are assumed to be truthfully answered. The average number of questions when asked in the most efficient sequence, to determine the chosen symbol, is ________ (rounded off to two decimal places).
| Symbols | a | b | c | d | e | f | g | h |
|---|---|---|---|---|---|---|---|---|
| Frequency of occurrence | 1/2 | 1/4 | 1/8 | 1/16 | 1/32 | 1/64 | 1/128 | 1/128 |
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 1.97 to 1.99
Explanation
The most efficient yes/no questioning has an average number of questions equal to the entropy (the probabilities are powers of 2, so a Huffman code meets it exactly): $H=\tfrac12(1)+\tfrac14(2)+\tfrac18(3)+\tfrac1{16}(4)+\tfrac1{32}(5)+\tfrac1{64}(6)+2\cdot\tfrac1{128}(7)=0.5+0.5+0.375+0.25+0.15625+0.09375+0.109375=1.984$, i.e. $1.98$.