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