GATE CSE 2007 | Question: 76

Question

Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \frac{1}{32}$, respectively. 

Which of the following is the Huffman code for the letter $a, \,b, \,c, \,d, \,e, \,f$?

• A. $0$, $10$, $110$, $1110$, $11110$, $11111$

• B. $11$, $10$, $011$, $010$, $001$, $000$

• C. $11$, $10$, $01$, $001$, $0001$, $0000$

• D. $110$, $100$, $010$, $000$, $001$, $111$

Answer 1

Based on the probabilities, we can say the probable frequency of the letters will be 

$16$, $8$, $4$, $2$, $1$, $1$

Now, the Huffman tree can be constructed as follows:

So, A is the answer for $76$.

https://en.wikipedia.org/wiki/Huffman_coding

Comments

@Arjun@srestha

Where to put two same weight?. Sir/ma'am i  did not get any information about that but i have seen many example they follow FCFS.

---

if (incoming weight  <= existing weight) then place(incoming weight on LEFT)

else place(incoming weight on RIGHT)

@Arjun sir please correct me if wrong.

---

Both the tree is correct. Right skewed will match here with the options.