Skip to main content

::: vuaskari.com ::: cs301 Assignment No. 4 Discussion & Solution

Assignment No. 4
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.

 




 

--
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
 
 

Comments

Post a Comment

Popular posts from this blog

Re: ::: vuaskari.com ::: CS408 - FINAL TERM SUBJECTIVE WITH REFERENCE SOLVED BY UMAIR SAULAT

GREAT WORK On Wed, Feb 20, 2013 at 11:30 PM, Umair Saulat < saulat.umair@gmail.com > wrote: CS408- Human Computer Interaction Solved Subjective Fall Semester 2012   QNo.1    it has been observed that most computer users use menu option for input instead of keyboard accelerator. What is the reason behind it? (2 Marks) Answer:- 1.        Menu options are easier to find. 2.        You don't have to memories the keys for menu option but for key board accelerators you have to memories them REF:: Handouts Page No. 127   QNo.2    Define active intervention.  (2 Marks) Answer:- Active intervention with the participant and actively probes the participant understands of whatever is being tested. REF:: Handouts Page No. 276 QNo.3    what is Ubiquitous Computing? (2 Marks) Answer:- The most profound technologies are those that disappear. They weave themselves into the fabric of everyday life until they are indi
Post a Comment
Read more

Updating our Google Account inactivity policy

Every day Google works hard to keep you and your private information safe and secure by preventing unauthorized access to your Google Account with our built-in security protections. And keeping you safe means having strong privacy practices across our products that minimize how long we store your personal files and any data associated with them. We want to protect your private information and prevent any unauthorized access to your account even if you're no longer using our services. Therefore, we are updating the inactivity period for a Google Account to two years across all our products and services. This change starts rolling out today and will apply to any Google Account that's been inactive, meaning it has not been signed into or used within a two-year period. An inactive account and any content in it will be eligible for deletion from December 1, 2023. What this means for you: These changes do not impact you unless you h
Post a Comment
Read more

Learn more about our updated Terms of Service

stargthb@gmail.com On January 5, 2022, we're making some changes to our Terms of Service. These changes won't affect the way you use Google services, but they'll make it easier for you to understand what to expect from Google — and what we expect from you — as you use our services. You can review the new terms here . At a glance, here's what this update means for you: More clarity on what you can expect from Google and what we expect from you : We're providing more examples to describe the mutually respectful conduct that we expect from all our users. Improved readability : While our terms remain a legal document, we've done our best to make them easier to understand, including reorganizing some topics so that they're easier to find. If you use Family Link to manage a Google Account for someone else, please take some time to talk to them about these changes. Thank you for using Google!
Post a Comment
Read more