cs301 Assigment # 2 Solution 2016

Assignment No. 02 (Graded)
Semester: Spring 2016

                                                             CS301: Data Structures

Joined Us On Facebook

 

Please read the following instructions carefully before submitting assignment.

It should be clear that your assignment will not get any credit if:

ü  The assignment is submitted after due date.

ü  The submitted assignment does not open or file is corrupt.

ü  Assignment is copied(partial or full) from any source (websites, forums, students, etc)

Uploading Instruction:

For clarity and simplicity, you are required to Upload/Submit only .doc file.

Objective:

The objectives of this assignment are:-

ü  To make students familiar with Huffman encoding algorithm

Problem Statement:

The organization ABC is a network forum that passes different type of messages over the network. The network will pass all the messages that are within the limit of network and when the message size cross the threshold value of networking, then it causes to memory overhead and that message will not be passed over the network.

Whenever we are trying to pass the given message, it causes to memory overhead.

Perfection is not attainable, but if we chase perfection we can catch excellence.

Now in order to pass the above message over the network, we have to compress the message. So your task is to compress the above message by using Huffman encoding technique.

In order to compress the above message by using Huffman encoding technique, you have to perform the following tasks:

1.      Create the frequency table

 

1.      Draw the binary tree on the basis of frequency table.

2.      What will be the size of the above message before compression?

3.      What will be the size of the above message after compression?

 

Solution :

Sol:

1.      Create the frequency table:z

Character	Frequency	Character	Frequency
NL	1	i	5
SP	12	l	3
,	1	n	6
.	1	o	3
P	1	p	1
a	6	r	2
b	2	s	2
c	8	t	7
e	12	u	1
f	3	w	2
h	2	x	1
Size:  82 characters(Space And Newline)

 

           

Character	Code	Character	Code
NL	011000	i	0111
SP	101	l	00001
,	011001	n	0101
.	011010	o	00100
P	011011	p	110000
a	0100	r	11001
b	00101	s	11010
c	111	t	0001
e	100	u	110001
f	00000	w	11011
h	00110	x	00111

1.      What will be the size of the above message before compression?

              Size of the message before compression: 82*8 = 656 bits.

2.      What will be the size of the above message after compression?

Size of the message after compression is 328 bits which is 50% less than the original message.