The Gateway to Computer Science Excellence
+20 votes

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$?

  1. $0$, $10$, $110$, $1110$, $11110$, $11111$

  2. $11$, $10$, $011$, $010$, $001$, $000$

  3. $11$, $10$, $01$, $001$, $0001$, $0000$

  4. $110$, $100$, $010$, $000$, $001$, $111$

in Algorithms by Veteran (52.3k points)
edited by | 3.1k views

1 Answer

+31 votes
Best answer

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$.

by Veteran (434k points)
edited by

Is there any constraint on where to put the two same weighted values according to them being single and composite? Is the following Huffman tree correct too?


@habedo007  it is correct.You will also get the same values,it just your tree can have left and right encoding of 1,0 opposite but it is also correct

@rahul sharma 5

If we give left -1, right - 0 on this particular tree, then 'f' will have 11110 which is diff from the option A

But then we could flip e & f to get the code for 'f' as 11111.


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.


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,726 answers
107,845 users