The Gateway to Computer Science Excellence
+19 votes
2.8k views

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.2k points)
edited by | 2.8k views

1 Answer

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

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

by Veteran (425k points)
edited by
+4

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?

0

@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

0
@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.
0

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

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,645 questions
56,562 answers
195,730 comments
101,646 users