PDA

View Full Version : CS301 Assignment # 4



Anya
06-28-2010, 08:16 PM
Question No: 1 Marks: 10


Show the result of inserting the following values into an empty AVL Tree.
You are required to show each step of insertion and rotation (to make the tree balance) in pictorial form with balance of each node.

19,21,22,17,18,23,27,25,30,34, 35


Question No: 2 Marks: 10

Find below some letters with their frequencies in a frequency table.



Frequency Table:
Character Frequency Character Frequency
A 1 O 4
C 1 R 2
D 3 J 1
E 7 N 6
F 2 S 1
G 1 T 3
W 1 NL 1
I 3 SP 6


a) Create a Huffman tree 4
b) Determine the binary code for each character 2
c) Encode the sequence ACDEF 2
d) Compare the Huffman encoded sequence of option c with the encoding of sequence with ASCII code. 2



Note:
More then one representations of Huffman encoding tree can be exist for the same data.

viki
06-28-2010, 10:34 PM
anya due date bhi mention kiya karain apni post mian when ever u post a assignment

ANI
07-01-2010, 03:55 AM
Aj last date hai is ki n kal bonus day hai....plzz i need it urgently ...cs301 ki assignmnet ka solution upload kr den .... God bless you...thanx in advance...:)

Guru
07-01-2010, 04:46 PM
Ani ek toh late post karti hoo aur uper sey shor bhi ... Kam sey kam time per post mara karo taky solution on time upload kar diya karen. I am uploading the solution now okay

Guru
07-01-2010, 04:59 PM
CS301 – Data Structures
Assignment No.4

Question 1:
Show the result of inserting the following values into an empty AVL Tree.
You are required to show each step of insertion and rotation (to make the tree balance) in pictorial form with balance of each node.

19,21,22,17,18,23,27,25,30,34, 35


Solution:

429

First we insert node 19 to make an AVL tree.then we insert 21 and compare its with root .This compare will rotate that 21 will goes to right subtree of 19.Then we compare 22 with 21 and this will also goes to right subtree of 21 Now let’s see the balance of nodes at this stage. We can see that the level of node 19 is at 0 level. But the difference of the height of left and right subtree of 19 is -2and that is unbalance.so we will rotate according to pictorial form.
Now we will insert new node 17.after comparing it with node 19 we will insert it as left subtree of 19. After that we will insert node 18 at right subtree of 19. Then node 23 at right subtree of 22.now we can see that tree is balance yet. But when we will insert node 27 at right subtree of 23 again tree will be unbalance.so we will rotate left.


Question 2

Guru
07-01-2010, 05:29 PM
Another Idea is attached just see the attached file

Awais
07-01-2010, 06:00 PM
Download the attachment