Register

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 42

• retagged by
826 views
11 votes
11 votes

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 strictly less than $1 / 3$, then Huffman's algorithm may produce a codeword of length $1.$
  • $\text{S2:}$ If the Huffman code of a character is ' $0$ ' or ' $1$ ', then the frequency of this character in the code is at least $50 \%$.

Which of the following is correct?

  1. $\mathrm{S} 1$ is true, and $\mathrm{S} 2$ is true.
  2. $\mathrm{S} 1$ is true, but $\mathrm{S} 2$ is false.
  3. $\mathrm{S} 1$ is false, but $\mathrm{S} 2$ is true.
  4. S1 is false, and S2 is false.
• retagged by
User Avatar

1 Answer

2 votes
2 votes
Answer: B

S2: If the Huffman code of some character is ' 0 ' or ' 1 ' then this character's frequency in the code is at least $50 \%$.

False.
Example 1: 'a' has freq. $1 / 100$, 'b' has freq. $99 / 100$, an optimal coding is 'a' gets '0' and ' $b$ ' gets ' 1 '.
Example 2; 'a' 'b' and 'c' each has freq. 1/3. an optimal coding: 'a'-'0', 'b'-'10', c-' 11 '.
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1.1k
views
1 answers
11 votes
GO Classes asked Jan 21
1,060 views
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 1
Consider the two statements regarding the Huffman's algorithm -$\text{S1:}$ The character with the highest probability (all probabilities are unique) is ... $\mathrm{S} 2$ is correctBoth are correct statementsBoth are incorrect statements
User Avatar
431
views
1 answers
5 votes
GO Classes asked Jan 28
431 views
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 41
Consider the following weighted graph, where the weight of every edge is written on the edge itself.What is the number of possible minimum spanning trees for the above graph?
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
Link Copied!