Assignment No. 02 (Graded) Semester: Spring 2016 CS301: Data Structures

	Assignment No. 02 (Graded) Semester: Spring 2016 CS301: Data Structures	Total Marks: 20 Due Date: 13/07 /2016 Lectures covered: 25 to 26
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: •        Create the frequency table •        Draw the binary tree on the basis of frequency table. •        What will be the size of the above message before compression? •        What will be the size of the above message after compression?

1, Frequency Table

Sr.no	Characters	Frequencies
1	A	6
2	B	2
3	C	8
4	E	12
5	F	3
6	H	2
7	I	5
8	L	3
9	N	6
10	O	3
11	P	2
12	R	2
13	S	2
14	T	7
15	U	1
16	W	2
17	X	1
18	SPACE	12
19	,	1
20	.	1
21	NEW LINE	1
22	TOTAL CHARACTERS	82

2, Binary Tree

3, What will be the size of the above message before compression?

Ans:- ASCII Character takes 8 bits (1 byte) to encode per character so the size of the message before compression is 8*82 = 656 bits.

4, What will be the size of the above message after compression?

Ans:- After using the huffman encoding the number of bits to encode per character is reduced to half which is 4 bits per character so the size of the message after compression is 50% lesser than the original size which is
4*82 = 328 bits.