CS301 VU Current Assignment No. 4 Spring 2013 Solution
Assignment No. 4
SEMESTER Spring 2013
CS301- Data Structures
Total Marks: 20
Due Date: 20/06/2013
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
SOLUTION:
12th steps to be taken on result of 13th is that AVL Tree
