GATE CSE 2021 Set 2 | Question: 26

Question

Consider the string $\textrm{abbccddeee}$. Each letter in the string must be assigned a binary code satisfying the following properties:

1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.
2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter.

Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?

• A. $21$
• B. $23$
• C. $25$
• D. $30$

Comments

We have to create a huffman tree, I was getting 23.

---

For those who are getting confused on the 2nd property, which is :

"For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter."

Everything revolves around the word: "at most in the statement".

At most means ' <= ' . So that means which ever letter/alphabet is coming first in the dictionary order will be assigned a codeword of length "at most" OR ' <= ' the length of the codeword assigned to the other letter which comes afterwards in the dictionary order. 

So this implies: len of code('d') >= len of code('c') >= len of code('b').

---

Important comment 

Answer 1

Given string: $abbccddeee$

$a$ has the least frequency and should be the leaf of the tree. $b,c$ and $d$ have the same frequency but as per Condition 2 in the questions $d$ should be taken first, followed by $c$ and then $b.$ $e$ has the highest frequency and so must be taken last.

$\begin{array}{|c|c|} \hline \textbf{Alphabet} & \textbf{Frequency} \\\hline  a  & 1  \\\hline  b & 2 \\\hline c & 2  \\\hline  d & 2 \\\hline e & 3 \\\hline \end{array}$

The final Huffman tree looks like:

$\begin{array}{|c|c|} \hline \textbf{Prefix Code} & \textbf{Code Length} \\\hline a = 000 & 3 \\\hline b =10 & 2 \\\hline c = 11 & 2 \\\hline d = 001 & 3 \\\hline e = 01 & 2 \\\hline \end{array}$

$\therefore$ Minimum length of encoded string: $(1*3)+(2*2)+(2*2)+(3*2)+(2*3)=23$

Option $B$ is correct.

References:

1. GATE 2007
2. ​GATE 2017
3. Huffman_coding wiki

Comments

Sir Why A , D together please clarify, I did not understand

---

@ayushjain321 its fine, you can combine a with any character with frequency=2, answer would still be the same.

---

Then what's the use of 2nd statement?

Irrespective of same answer , we should solve the way it should be.

#kuch_bhi

Answer 2

Answer is $23$.

It is a Huffman tree problem with the only constraint that the depth of node $d$ $\ge$ node $c$ $\ge$ node $b$.

So while creating the tree, node $a$ can only be joined with node $d$. And node $b$ and $c$ have to be joined together. 

Comments

But according to the solution given shouldn’t b have a code with the max length then c then d? as in dictionary order, it is b → c → d

pls clarify