GATE CS 2007 Q77 — Algorithm Design: Greedy Techniques

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

1. Initial probabilities: $a: \frac{16}{32}$, $b: \frac{8}{32}$, $c: \frac{4}{32}$, $d: \frac{2}{32}$, $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{2}{32}$.
3. Merge $d$ ($\frac{2}{32}$) and $ef$ ($\frac{2}{32}$) to form parent node $def$ with probability $\frac{4}{32}$.
4. Merge $c$ ($\frac{4}{32}$) and $def$ ($\frac{4}{32}$) to form parent node $cdef$ with probability $\frac{8}{32}$.
5. Merge $b$ ($\frac{8}{32}$) and $cdef$ ($\frac{8}{32}$) to form parent node $bcdef$ with probability $\frac{16}{32}$.
6. Merge $a$ ($\frac{16}{32}$) and $bcdef$ ($\frac{16}{32}$) to form the root with probability $1$.

From this tree, the code lengths ($l_i$) for each letter are:

• $a$: $1$ bit
• $b$: $2$ bits
• $c$: $3$ bits
• $d$: $4$ bits
• $e$: $5$ bits
• $f$: $5$ bits

The average code length ($L$) is calculated as:

Thus, the average length of the Huffman code is $1.9375$.