GATE CSE
First time here? Checkout the FAQ!
x
0 votes
231 views

The following data contains 100 symbols.
If Huffman coding is applied to the given data

 

 

What is the code for the letter ‘E’ if ‘0’ as taken left and ‘1’ is right

A. 101

B. 100

C. 110

D. 111

asked in Algorithms by Active (2.4k points) 3 16 42 | 231 views
I m getting 000
I am also getting 000 but in answer key it is showing as 100.

3 Answers

+1 vote
Best answer

Answer will be either 000 or 111. it depends whether we keep Small Values at LHS and Larger Value at RHS or vice versa:

If we keep larger frequency value at LHS and small Value at RHS then 111 is the correct answer:

answered by Veteran (16.4k points) 15 134 252
selected by

Nice explanation @ Vijay Thakur . Here 111 is not possible because in question it has been said that 0 to be taken left. 

What happens if we arrage  frequency in descending order and construct the tree ? In this case Im getting 101 . Is it wrong ?
@Anup Patel see my updated solution

Right Answer is Shown as 100. I think there is some error in Options. 

Note Regarding Updated Solution : I think in huffman coding we keep Small Values at left side and large value at right side , we can just assign Value 0 or 1 to Left/Right as per our assumption.

Can someone explain What is the algorithm to form the tree in Huffman Coding ?
What I knew is
At every time we will take  least two probabilities of the numbers after arranging them in ascending order and make min heap .  We will do it iteratevely .

Is it true that when we instertting new symbols also shoudnt we consider this ?
0 votes

Hope this will help

 

answered by (105 points) 3
I am waiting for Reply From Ravindrababu Ravula sir Regarding this question . I think there is error in options.
57 is larger value and you kept it at LHS and 43 is smaller value than 57 amd you kept 43 at RHS, ok no problem but in case of 18 and 25. 25 is larger than 18 but you kept it at RHS and 18 at LHS, why??
0 votes
I am getting 000 of "E" letter but answer keys are not matched.
answered by Active (1.3k points) 1 2 16


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
Top Users Oct 2017
  1. Arjun

    23240 Points

  2. Bikram

    17038 Points

  3. Habibkhan

    7096 Points

  4. srestha

    6008 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4928 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4278 Points

  9. sushmita

    3954 Points

  10. Rishi yadav

    3744 Points


Recent Badges

Popular Question neha singh
Notable Question tajar
Notable Question Imarati Gupta
Notable Question set2018
Popular Question jothee
Notable Question set2018
Notable Question Pavan Kumar Munnam
Notable Question iarnav
Popular Question makhdoom ghaya
Popular Question Satyam
27,254 questions
35,075 answers
83,756 comments
33,185 users