GATE CSE 2017 Set 2 | Question: 50

Question

A message is made up entirely of characters from the set $X=\{P, Q, R, S, T\}$. The table of probabilities for each of the characters is shown below:$$\begin{array}{|c|c|}\hline \textbf{Character}  &  \textbf{Probability } \\\hline  \text{$P$} & \text{$0.22$} \\  \text{$Q$} & \text{$0.34$} \\  \text{$R$} & \text{$0.17$} \\ \text{$S$} & \text{$0.19$} \\  \text{$T$} & \text{$0.08$} \\ \hline\text{Total} & \text{$1.00$} \\\hline  \end{array}$$If a message of $100$ characters over $X$ is encoded using Huffman coding, then the expected length of the encoded message in bits is ______.

Comments

this is in network ..vol 3

---

https://gateoverflow.in/43513/gate2007-77 

note the difference :)

---

ROOT node should be of 100 because sum of all character i.e P,Q,R,S,T is 100 and it totally wrong that you r getting 200..

Answer 1

$X = \{ P, Q, R, S, T\}$

$∴ \text{Expected length of an encoded character}$
$\qquad \qquad= (0.22 \times 2) + (0.34 \times 2) + (0.17 \times 3) + (0.19 \times 2) + (0.08 \times 3) \hspace{0.1cm} \text{ bits }$
$\qquad \qquad= 0.44 + 0.68 + 0.51+ 0.38 + 0.24 \hspace{0.1cm} \text{ bits}$
$ \qquad \qquad= 2.25 \hspace{0.1cm} \text{ bits } $

$\therefore \text{Expected length of a encoded message of $100$ characters in bits} = 100 \times 2.25 = 225$

Comments

@chauhansunil20th

it's very silly i think, how avg length of 100 character would be 2.25, if the characters are distinct. For one character you need at least 1 character to encode, isn't it. Some character vary by their prefix so it always be > 100. And if they ask avg length required by per character then this is a different context , 

hence it would be (weighted external path length / total frequency of each character )

---

Thank you sir
Your point important most of us make this mistake

---

Useful to know: -

Expected length of an encoded character = The total probability

= Sum of internal nodes $ = 1+0.41+0.59+0.25 = 2.25$

Hence expected length of encoded msg $ = 2.25*100 = 225$ 

Answer 2

so ans is 225

Comments

@loyal

I understood your tree solution .

Please help me in understanding what is difference between average length and average lengthy per character and how do we get to know in question we have to find which one avg lenght or avg length per character.

---

@mayank I also have the same doubt if the expected length is asked then answer should be 225/100 = 2.25, expected means average value.

---

@Rupendra @akash

Rupendra's comment should be added in the best answer.

As it is the mistake done by 90% people including me.

Answer 3

To create the Huffman tree, always increase the nodes in ascending order, and merge the first two nodes.

Step 1)

Given: $\begin{bmatrix} P & Q &R &S &T \\ 0.22 &0.34 &0.17 &0.19 &0.08 \end{bmatrix}$ → $\begin{bmatrix} T & R &S &P &Q \\ 0.08 &0.17 &0.19 &0.22 &0.34 \end{bmatrix}$ → $\begin{bmatrix} TR &S &P &Q \\ 0.25 &0.19 &0.22 &0.34 \end{bmatrix}$

 

Step 2)

$\begin{bmatrix} TR &S &P &Q \\ 0.25 &0.19 &0.22 &0.34 \end{bmatrix}$ → $\begin{bmatrix} S &P&TR &Q \\ 0.19 &0.22 &0.25 &0.34 \end{bmatrix}$ → $\begin{bmatrix} SP&TR &Q \\ 0.41 &0.25 &0.34 \end{bmatrix}$

 

Step 3)

$\begin{bmatrix} SP&TR &Q \\ 0.41 &0.25 &0.34 \end{bmatrix}$ → $\begin{bmatrix} TR&Q &SP \\ 0.25 &0.34 &0.41 \end{bmatrix}$ → $\begin{bmatrix} TRQ &SP \\ 0.59 &0.41 \end{bmatrix}$

 

Step 4)

Finally merge these two.

---

Hence, the Huffman Tree would look like this:-

$(0.22*2)+(0.34*2)+(0.19*2)+(0.17*3)+(0.08*3)=2.25$

Length  2.25 per character. Given, there are 100 characters in the message, so,

$2.25*100=225$

---

225

Comments

Detailed and clean <3

---

Thanks sir , the first method is very helpful

---

Thanks bro! yours one is the one with most clarity, I was having problem with grouping in huffman coding, you cleared all my doubts

Answer 4

Answer-225

Comments

Yes!

---

225 is right ans as they have asked for expected length for endcoded msg and msg conatins 100 char.