|
| Assignment No. 4 |
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]
. 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. | |||||||||||||
|
| |||||||||||||
We say, "Be one as Pakistani Nation and grow up for Pakistan's Future". Wish you all the best. Join www.vuaskari.com,
To post to this group, send email to vuaskari_com@googlegroups.com
Visit these groups:
This (Main) Group:http://groups.google.com/group/vuaskari_com?hl=en?hl=en
MIT/MCS Group: http://groups.google.com/group/vu_askarimit?hl=en?hl=en
HRM Group: http://groups.google.com/group/askari_hrm?hl=en?hl=en
Banking Group: http://groups.google.com/group/askari_banking?hl=en?hl=en
Management: https://groups.google.com/group/vuaskari_mgt?hl=en
Marketing: https://groups.google.com/group/vuaskari_mkt?hl=en
MIS Group: http://groups.google.com/group/askari_mis?hl=en
No comments:
Post a Comment
PLEASE COMMENT ABOUT YOUR VISIT AND MY SITE
Note: Only a member of this blog may post a comment.