/ Assignment No. 03(Graded)
SEMESTER Fall 2014
CS301- Data Structures / Total Marks: 20
Due Date: 09/02/2015
Instructions
Please read the following instructions carefully before solving & submitting assignment:
It should be clear that your assignment will not get any credit (zero marks) if:
  • The assignment is submitted after due date.
  • The submitted assignment is other than .doc file.
  • The submitted assignment does NOT open or file is corrupted.
  • The assignment is copied (from other student or ditto copy from handouts or internet).
Uploading instructions
  • For clarity and simplicity, you are required to Upload/Submit only .doc/.docx file.
Objective
The objective of this assignment is:
  • To give you the practical implementation of Huffman Encoding Technique.
For any query about the assignment, contact at
GOOD LUCK
Marks: 20
Problem Statement:
Suppose you are hired as aNetwork programmer by a leading software company with a task to enhance the data transferring speed over a communication line. Note that there are two ways to perform the required task:
  1. To increase the bandwidth
  2. To minimize the size of data using any encoding technique.
Due to some financial reasons, the company is not able to enhance their bandwidth;therefore the only choice is to minimize the size of data using some bits encoding technique.
Following are the two indicators which must be encountered while performing your task:
Data should not be lost in any way.
Privacy of data must be ensured.
You have studied the Huffman encoding technique in this course; you are required to use the said technique to solve the given problem. In order to test your application, encode the following sentence using Huffman encoding technique:
MY NETWORK APPLICATION IS WORKING PROPERLY
Tasks you have to do:
Keeping in mind the above scenario for the exemplary sentence, give answers of the following questions.
  1. Construct the frequency table for all the letters given in the sentence excluding new line character.
  2. Construct Huffman tree for the given sentence.
  3. Construct Huffman code table for each letter.
  4. Prove mathematically that how much percentage of bandwidth is saved by Huffman technique as compared to ASCII encoding scheme (ASCII is encoding scheme that represent each character as 8 bits).

Lectures Covered: This assignment covers Lecture # 24-26
Deadline: Your assignment must be uploaded/submitted at or before. Feb 9 , 2014