The Gateway to Computer Science Excellence

+21 votes

Suppose the letters $a, \,b, \,c, \,d, \,e, \,f$ have probabilities $\dfrac{1}{2}, \dfrac{1}{4}, \dfrac{1}{8}, \dfrac{1}{16}, \dfrac{1}{32}, \dfrac{1}{32}$, respectively.

What is the average length of the Huffman code for the letters $a, \,b, \,c, \,d, \,e, \,f$?

- $3$
- $2.1875$
- $2.25$
- $1.9375$

+28 votes

Best answer

$$\begin{array}{|c|c|} \hline \textbf{Letter} & \textbf{Probability} \\\hline a & 1/2 \\\hline b & 1/4 \\\hline c & 1/8 \\\hline d & 1/16 \\\hline e & 1/32 \\\hline f & 1/32 \\\hline \end{array}$$

$\begin{array}{cc} \textbf{Prefix Code} & \textbf{Code Length} \\ a = 0 & 1 \\ b =10 & 2 \\ c = 110 & 3 \\ d = 1110 & 4 \\ e = 11110 & 5 \\ f = 11111 & 5 \end{array}$

Avg length $= \dfrac{1}{2} \times 1 + \dfrac{1}{4} \times 2+ \dfrac{1}{8} \times 3+ \dfrac{1}{16} \times 4+ \dfrac{1}{32} \times 5+ \dfrac{1}{32} \times 5 \\ = \dfrac{16 + 16 + 12 + 8 + 5 + 5}{32} \\ = 1.9375 $

Correct Answer: $D$

+13 votes

Based on the probabilities, we can say the probable frequency of the letters will be

16, 8, 4, 2, 1, 1

Now, the Huffman tree can be constructed as follows:

Average length will be 1/2 * 1 + 1/4 * 2 + 1/8 * 3 + 1/16 * 4 + 1/32 * 5 + 1/32 * 5

= 62/32 = 1.9375

https://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html

0

Because not all the letters occur with same frequency or probability. Purpose of Huffman encoding is to represent the most occurring character with least number of bits. As u can see a has been represented with only 1 bit because it occurs the most with probability 1/2. So we need to multiply length of bits with the probability with which they occur.

0

After calculating like arjun sir, we can even multiply with probably frequencies like this: 16*1 + 8*1 + 4*3 + 2*4 +1*5*2 / 16+ 8+4+2+1+1 = 1.9375

0

@Arjun sir,

for such huffman coding question sometimes sees confusong, Sir can you please check this is right or wrong

1) Expected Length of Huffman Code for N chars (Frequencies given ) =

$\sum$(Bits needed for char * its frequency)

2) Average Length Of Huffman Code for N characters OR Average Bits needed for N characeters = (Assuming average over N characters)

[ $\sum$(Bits needed for char * its frequency) ] / Total characters

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,508 answers

195,534 comments

100,975 users