in Algorithms retagged by
644 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.
in Algorithms retagged by
644 views

4 Comments

@Sachin Mittal 1 Please update answer in final key!

0
0
^ It has been done.
1
1

$ \large{\colorbox{yellow}{Detailed video solution of this question with direct time stamp}}$

All India Mock Test 4 - Solutions Part 1

0
0

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 '.
Answer:

Related questions