HuffmanCoding
Question 1 
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:
If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is __________.
225  
226  
227  
228 
Question 1 Explanation:
General procedure to solve Huffman coding problem
Step1: Arrange into either descending/ ascending order according to that profits.
Step2: Apply optimal merge pattern procedure.
Step3: Make left subtree value either 0 or 1, for right subtree, viceversa.
= 2 × 0.34 + 2 × 0.22 + 2 × 0.19 + 3 × 0.17 + 3 × 0.08
= 2.25
∴ So, for 100 characters, 2.25 * 100 = 225
Question 2 
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?
0, 10, 110, 1110, 11110, 11111
 
11, 10, 011, 010, 001, 000
 
11, 10, 01, 001, 0001, 0000
 
110, 100, 010, 000, 001, 111

Question 2 Explanation:
→ 0, 10, 110, 1110, 11110, 11111
Question 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?
3  
2.1875
 
2.25  
1.9375

Question 3 Explanation:
The Average length =(1*1/2+2*1/4+3*1/8+4*1/16+5*1/32+5*1/32)=1.9375
There are 3 questions to complete.