# 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

# Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.