GATE CS 1989 Q13a — Algorithm Design: Greedy Techniques

To minimize the average length of the encoded words, we use Huffman Coding, which generates an optimal prefix binary code.

We start with the given frequencies of the letters:

• $b: 0.05$
• $d: 0.08$
• $f: 0.11$
• $c: 0.17$
• $a: 0.19$
• $e: 0.40$

Step-by-step Huffman Tree Construction:

1. Combine the two lowest frequencies, $b(0.05)$ and $d(0.08)$, to form a node $bd(0.13)$.
2. Combine the next two lowest frequencies, $f(0.11)$ and $bd(0.13)$, to form a node $fbd(0.24)$.
3. Combine $c(0.17)$ and $a(0.19)$ to form a node $ca(0.36)$.
4. Combine $fbd(0.24)$ and $ca(0.36)$ to form a node $fbdca(0.60)$.
5. Finally, combine $e(0.40)$ and $fbdca(0.60)$ to form the root node $(1.00)$.

The resulting tree structure yields the following code word lengths (depths from the root):

• $e$: depth $1$ (frequency $0.40$)
• $c$: depth $3$ (frequency $0.17$)
• $a$: depth $3$ (frequency $0.19$)
• $f$: depth $3$ (frequency $0.11$)
• $b$: depth $4$ (frequency $0.05$)
• $d$: depth $4$ (frequency $0.08$)

Average Code Word Length ($L$):