Skip to content
GATEiit

GATE CSE 2021 Set 2 Q36: Minimum encoded length of abbccddeee with a prefix code

Question

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

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: B (official GATE 2021 final answer key)

Concept used: Huffman coding gives the minimum total length of a prefix code; ties can be broken to satisfy the ordering rule without changing the total.

First step: Frequencies are a:1, b:2, c:2, d:2, e:3; run Huffman, merging a with d (the last of the tied letters) first.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2021 Set 2 questions →