Assignment No. 4 SEMESTER Spring 2013 CS301- Data Structures

[Xpert]

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:

[FONT=&quot]1. [/FONT]Build a table containing the following information about the string. [2]

Characters

Frequency

.
[FONT=&quot]2. [/FONT]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]

[FONT=&quot]3. [/FONT]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.