Huffman-Coding

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 __________.

 
A
225
B
226
C
227
D
228
       Algorithms       Huffman-Coding       GATE 2017(set-02)
Question 1 Explanation: 

General procedure to solve Huffman coding problem
Step-1: Arrange into either descending/ ascending order according to that profits.
Step-2: Apply optimal merge pattern procedure.
Step-3: Make left sub-tree value either 0 or 1, for right sub-tree, vice-versa.




= 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?
A
0, 10, 110, 1110, 11110, 11111
B
11, 10, 011, 010, 001, 000
C
11, 10, 01, 001, 0001, 0000
D
110, 100, 010, 000, 001, 111
       Algorithms        Huffman-Coding       Gate-2007
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?  
A
3
B
2.1875
C
2.25
D
1.9375
       Algorithms        Huffman-Coding       Gate-2007
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.
PHP Code Snippets Powered By : XYZScripts.com