ISRO CSE 2020 | Question: 34

Question

Huffman tree is constructed for the following data :$\{A,B,C,D,E\}$ with frequency $\{0.17,0.11,0.24,0.33\ \text{and} \ 0.15 \}$ respectively. $100\ 00\ 01101$ is decoded as

• A. $BACE$
• B. $CADE$
• C. $BAD$
• D. $CADD$

Answer 1

There's a typo in the huffman code. It should be 100 00 01 101.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

100 - B
00 - A
01 - C
101 - E

BACE

Option A 

Comments

Brpo how will be sure that D will hae to be in left subtree only and not the rigt subtree within the roots right child?

---

I think becoz, 0.33 is  more close to 0.26 rather than 0.41

Answer 2

100 00 01101 is decoded as BACE

Comments

can we interchange left and right subtree of root ? does it affect in encoding?

---

No it can not  be changed because according to huffman coding the left side is lower child and right onee is bigger child.

---

Heisenbergg, there is nothing like while drawing Huffman coding we need to follow this binary search tree idea, we can draw it only using binary tree, and the numbering of zero and one solely depends on the person. In question, they should have mentioned those points which need to be taken care of while drawing the tree

---

you can swap subtrees; it will alter bit patterns but not encoding efficiency. ,therefore they should have mentioned it .(its ambiguous)

Answer 3

Ans

Comments

this is the only valid explaination

 

Answer 4

This can be a lengthy question if solved manually because you have to check for multiple combinations.
A better way to get the answer: the final codeword must contain B and E, because both have codewords of length 3 (their combined frequency is the lowest). The rest (A, C, D) have codewords of length 2.

given options have 4 letters only. So, to make the total codeword length (100 00 01101) = 10, we must choose B, E, and two of A, C, D.
Therefore, option a is the right answer.
in option c there are three letters so its not possible using length of   {b,e}=3 , {a,c,d} = 2.