/ Assignment No. 04
SEMESTER Spring 2014
CS301- Data Structures / Total Marks: 20
Due Date: 17/07/2014
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 file is other than .doc or docx format.
 The submitted assignment file does not open or 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 one .doc /.docx file.
 Don’t wait for grace day. Grace Day is given only if there is problem with LMS on due date. Submit your solution within due date.
 Note that no assignment will be accepted through email if there is any problem on grace day.
Note: Use only MS Word.
Objective
The objective of this assignment is to make you familiar with the compression and compression technique like Huffman Encoding.
For any query about the assignment, contact at
GOOD LUCK
Marks: 20
Mr. Hamid and Mr. Nisar are working as Detective in an investigation unit of a sensitive institution. They are assigned a very important and complex case to solve. Being an IT professional, you are assigned to help them in anyway. Mr. Hamid has to go outstation in search of a clue. He has found some important points and wants to send them to Nisar via email. Now as the secrecy is the base of the investigation, he has used the code words for the message. The file size is huge. Mr. Hamid wants to send the file as quickly as possible. The heavy files take more time for transmission than small ones. He wants you to compress the message so it can be send rapidly. Suppose the message is;
Deer is dear but dear
How will you encode this message using Huffman encoding for Mr. Nisar?
You are required to show the frequency table, Huffman tree and the encoded message.
Solution Guidelines:
  1. First understand the need of compression.
  2. Make frequency table of the given line by following the method given in handouts.
  3. Build Huffman tree as instructed.
  4. From the tree, note the codes of the alphabets and encode the message.
  5. Do not use newline character during the compression.

Lectures Covered: This assignment covers Lecture # 20-26
Deadline: Your assignment must be uploaded / submitted on / before, Thursday, July 17, 2014.