# Cs301 Assignment 2 Solution Spring 2022

CS301 Assignment 2 Solution Spring 2022

Do not wait for grace day. Grace day is given only if there is problem with LMS on due date. Submit your solution within due date. The objective of this assignment is to get hands on practice . Construction of frequency table. Construction of Huffman Encoding tree. Checking efficiency of Huffman encoding compression technique.

Problem Statement:

A competition of best quotes is being held in an educational institute. Administration of the institute will collect the quotes messages from students over the internet as a text file. A task assigned to you is to use the Huffman encoding technique and build a binary tree that will be used to encode and decode the content of text files. Consider the message given below that is saved in text files and received through the internet. You have to build a frequency table and Huffman encoding binary tree. Furthermore, calculate the efficiency of this encoding technique and calculate how much bandwidth is saved for compressing the files messages of 10,000 students.

Solution Instructions:

You need to perform following step by step tasks to compress the message, calculate the efficiency and find bandwidth saved for the messages of 10,000 students:

• Count all the letters including space from the given text message.
• Draw a table with column names (letter, frequency, original bits, encoded bits)
• Fill the table with letters, frequency, original bits (for original bits get ASCII decimal code of each letter, convert the decimal ASCII into 8 bits binary code) and encoded bits (these can be found from Huffman encoding tree as mentioned in point 5).
• Draw final Huffman encoding tree with the help of frequency table. (Step by step construction of Huffman encoding tree is not required, just show the final tree in the solution file).
• Get the encoded bits from tree and fill code of each letter in last column of table constructed in step 2.
• Calculate the efficiency of Huffman encoding technique.
• (For efficiency use total original bits, total compressed (encoded) bits and find what percentage of memory is saved with the help of Huffman encoding technique).
• For the calculation of bandwidth saved for 10,000 messages, use the calculation performed in step 6.  