Skip to content
GATETECH
Official PYQ · 2021Set 2 · Q26Algorithm Design: Greedy TechniquesMCQ2 marks

GATE CS 2021 Set 2 Q26 — Algorithm Design: Greedy Techniques

Explain with AI

Consider the string abbccddeee\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?

Choose one option
View worked solution

Answer: B

First, let us determine the frequencies of each character in the string abbccddeee:

  • a:1a: 1
  • b:2b: 2
  • c:2c: 2
  • d:2d: 2
  • e:3e: 3

By constructing a standard Huffman tree, the optimal set of code lengths (depths) for these frequencies is found to be {3,3,2,2,2}\{3, 3, 2, 2, 2\}. The absolute minimum length of the encoded string under any prefix-free code is:

Minimum Length=1(3)+2(3)+2(2)+2(2)+3(2)=23\text{Minimum Length} = 1(3) + 2(3) + 2(2) + 2(2) + 3(2) = 23

Now, we must satisfy Property 2: for characters with the same frequency (b,c,db, c, d), their code lengths must satisfy L(b)≤L(c)≤L(d)L(b) \le L(c) \le L(d) since they are alphabetically ordered as b<c<db < c < d.

We can assign the optimal set of lengths {3,3,2,2,2}\{3, 3, 2, 2, 2\} to the characters as follows:

  • L(a)=3L(a) = 3
  • L(b)=2L(b) = 2
  • L(c)=2L(c) = 2
  • L(d)=3L(d) = 3
  • L(e)=2L(e) = 2

This assignment satisfies both properties:

  1. It is a valid prefix-free code (since the set of depths is {3,3,2,2,2}\{3, 3, 2, 2, 2\}).
  2. For same-frequency characters b,c,db, c, d, we have L(b)≤L(c)≤L(d)L(b) \le L(c) \le L(d) (i.e., 2≤2≤32 \le 2 \le 3).

The total encoded length remains:

1(3)+2(2)+2(2)+2(3)+3(2)=3+4+4+6+6=231(3) + 2(2) + 2(2) + 2(3) + 3(2) = 3 + 4 + 4 + 6 + 6 = 23

Since 23 is the absolute lower bound for any prefix code with these frequencies, the minimum length of the encoded string is 23.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Algorithm Design: Greedy Techniques questions