GATE CS 2007 Q76 — Algorithm Design: Greedy Techniques

To find the Huffman code, we construct the Huffman tree by repeatedly merging the two nodes with the smallest probabilities:

1. Initial probabilities: $a: \frac{1}{2}$, $b: \frac{1}{4}$, $c: \frac{1}{8}$, $d: \frac{1}{16}$, $e: \frac{1}{32}$, $f: \frac{1}{32}$.
2. Merge $e$ and $f$ (each $\frac{1}{32}$) to form parent node $ef$ with probability $\frac{1}{16}$.
3. Merge $d$ ($\frac{1}{16}$) and $ef$ ($\frac{1}{16}$) to form parent node $def$ with probability $\frac{1}{8}$.
4. Merge $c$ ($\frac{1}{8}$) and $def$ ($\frac{1}{8}$) to form parent node $cdef$ with probability $\frac{1}{4}$.
5. Merge $b$ ($\frac{1}{4}$) and $cdef$ ($\frac{1}{4}$) to form parent node $bcdef$ with probability $\frac{1}{2}$.
6. Merge $a$ ($\frac{1}{2}$) and $bcdef$ ($\frac{1}{2}$) to form the root node with probability $1$.

Assigning 0 to the left branch and 1 to the right branch at each step of the tree yields the following prefix codes:

• $a$: $0$
• $b$: $10$
• $c$: $110$
• $d$: $1110$
• $e$: $11110$
• $f$: $11111$

This matches the code sequence given in Option A.