# Greedy Algorithms Quiz 3

**Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes?**

A. 3

B. 2.1875

C. 2.25

D. 1.9375

# Solution :

D) is correct.

We get the following Huffman Tree after applying Huffman Coding Algorithm. The idea is to keep the least probable characters as low as possible by picking them first.

The letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.

` 1`

/ \

/ \

1/2 a(1/2)

/ \

/ \

1/4 b(1/4)

/ \

/ \

1/8 c(1/8)

/ \

/ \

1/16 d(1/16)

/ \

e f

The average length = (1*1/2 + 2*1/4 + 3*1/8 + 4*1/16 + 5*1/32 + 5*1/32) = 1.9375