GATE CS 2017 Set 2 Q50 — Algorithm Design: Greedy Techniques

To find the expected length of the encoded message, we first construct the optimal prefix-free binary tree using Huffman Coding.

Step 1: List the characters and their probabilities

Arrange the characters in ascending order of their probabilities:

• $T: 0.08$
• $R: 0.17$
• $S: 0.19$
• $P: 0.22$
• $Q: 0.34$

Step 2: Construct the Huffman Tree

1. Combine the two smallest probabilities: $T (0.08)$ and $R (0.17)$.
   • New internal node $(TR) = 0.08 + 0.17 = 0.25$.
   • Remaining set: $S(0.19), P(0.22), (TR)(0.25), Q(0.34)$.
2. Combine the next two smallest: $S (0.19)$ and $P (0.22)$.
   • New internal node $(SP) = 0.19 + 0.22 = 0.41$.
   • Remaining set: $(TR)(0.25), Q(0.34), (SP)(0.41)$.
3. Combine the next two smallest: $(TR) (0.25)$ and $Q (0.34)$.
   • New internal node $(TRQ) = 0.25 + 0.34 = 0.59$.
   • Remaining set: $(SP)(0.41), (TRQ)(0.59)$.
4. Combine the final two nodes: $(SP) (0.41)$ and $(TRQ) (0.59)$.
   • Root node $= 0.41 + 0.59 = 1.00$.

Step 3: Determine the Code Lengths

By tracing the paths from the root to each leaf node, we find the length (number of bits) for each character:

• P (from root $\to$ $SP$ $\to$ $P$): $2$ bits
• Q (from root $\to$ $TRQ$ $\to$ $Q$): $2$ bits
• R (from root $\to$ $TRQ$ $\to$ $TR$ $\to$ $R$): $3$ bits
• S (from root $\to$ $SP$ $\to$ $S$): $2$ bits
• T (from root $\to$ $TRQ$ $\to$ $TR$ $\to$ $T$): $3$ bits

Step 4: Calculate the Expected Length

The expected length of a single character ($L$) is given by:

For a message containing $100$ characters, the expected length of the entire encoded message is: