CS301 Assignment # 4

[Anya]

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]

anya due date bhi mention kiya karain apni post mian when ever u post a assignment

[ANI]

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]

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]

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:


  CS301.jpg (Size: 23.93 KB / Downloads: 138)

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]

Another Idea is attached just see the attached file

[Awais]

Download the attachment