Register

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 1

• retagged by
1,060 views
11 votes
11 votes

Consider the two statements regarding the Huffman's algorithm -

  • $\text{S1:}$ The character with the highest probability (all probabilities are unique) is guaranteed to be one of the leaves that is closest to the root (i.e it has the least depth among all leaves).
  • $\text{S2: }$if all characters occur with probability less than $1 / 3$, then there is guaranteed to be no codeword of length $1.$

Which of the following is CORRECT?

  1. $\mathrm{S} 1$ is correct but $\mathrm{S} 2$ is false
  2. $\mathrm{S} 1$ is false but $\mathrm{S} 2$ is correct
  3. Both are correct statements
  4. Both are incorrect statements
• retagged by
User Avatar

1 Answer

5 votes
5 votes

In Huffman’s algorithm, the character with the highest probability (all probabilities are unique) is guaranteed to be one of the leaves that is closest to the root (i.e it has the least depth among all leaves).

True
https://hkn.eecs.berkeley.edu/examfiles/cs170_fa07_mt2_sol.pdf

if all characters occur with a probability less than $1/3,$ then there is guaranteed to be no codeword of length $1.$

True
https://inst.eecs.berkeley.edu/~cs170/fa18/assets/dis/dis05-sol.pdf

• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

827
views
1 answers
11 votes
GO Classes asked Jan 28
827 views
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 42
Consider the following statements related to Huffman's algorithm:$\text{S1:}$ If there is exactly one symbol with a frequency of $1 / 3$, and all other symbols have frequencies ... , but $\mathrm{S} 2$ is true.S1 is false, and S2 is false.
User Avatar
950
views
1 answers
2 votes
Bikram asked Feb 9, 2017
950 views
Test by Bikram | Mock GATE | Test 3 | Question: 35
Consider the following set of messages with their frequencies: ... for total binary stream transmission using Huffman Encoding over simple encoding is _______ %.
User Avatar
4.5k
views
1 answers
0 votes
Na462 asked Apr 30, 2018
4,513 views
MadeEasy Test Series: Algorithms - Greedy Algorithm
Consider the following message:The number of bits required for huffman encoding of the above message are __________?My Strategy:- But the answer given is 52bits i used standard Algorithem Made Easy Solution :-
User Avatar
Link Copied!