CS301-Data Structures Assignment No.4 Discussion And Solution Spring 2013 Due Date: June-20-2013

SEMESTER Spring 2013
CS301- Data Structures
Total Marks: 20

Due Date: 20/06/2013
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:
o The assignment is submitted after due date.
o The submitted assignment is other than Ms Word 2003 file.
o The submitted assignment does NOT open or file is corrupted.
o 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 Ms Word file (.doc or docx format).

Note: Use ONLY Microsoft Word
Objective
The objective of this assignment is,

o To make you familiar with construction of AVL Tree Data Structure.
o To make you familiar with concept of Huffman Encoding.


For any query about the assignment, contact at cs301@vu.edu.pk
GOOD LUCK

Assignment Statement: Marks: 20


Question 1: [Marks 10]

You are required to construct an AVL tree from the following data.

20, 40, 30, 19, 21, 22, 41, 45, 25 , 24, 26, 18

You need to insert these data items one by one starting from left (data item 20) in the same order in which they have written above.

Mention all the intermediate steps and perform rotations that will be carried out while constructing an AVL tree from the above data.










Question 2: [Marks 10]

The transmission speed of data over the network can be increased in two ways; either increases the bandwidth of communication channel or decrease the size of data (compression) to increase the bandwidth utilization.
We can use different algorithms for compression. In compression, we don’t want to lose our data. Huffman encoding scheme is used for lossless data compression.
Suppose the following string is being transmitted over the network:

“data structures is very interesting”

We cannot increase the given bandwidth of communication channel. Instead we have to compress the given string. Use Huffman encoding scheme to encode the given string.

To encode the string:

1. Build a table containing the following information about the string. [2]

Characters Frequency





.
2. Build Huffman encoding tree. The tree will be build with the help of characters and their respective frequencies which you will find in step 1. [6]

3. Calculate how much bits are consumed by original and compressed string. What percentage of bits is saved by Huffman encoding scheme? [2]

Mention step by step construction of Huffman Encoding tree from the above table.





Lectures Covered: This assignment covers Lecture 16-26.
Deadline: Your assignment must be uploaded/submitted at or before 20/06/2013.