B.

TECH - CS
Assignment - 2
Semester-V (Odd), Session: 2023-24
KCS-503: Design and Analysis of Algorithm
Unit-2 Course Outcome: CO2 – Find an
Unit-Name Advanced Data Structures algorithm to solve the problem (create) and
prove that the algorithm solves the problem
correctly (validate).

Date of Distribution: 16/10/2023 Faculty Name: Mr. Vinay Singh

Sr. MANDATORY QUESTIONS BL

1 Explain RB Tree with its various properties in brief. 1
2 Prove that height of any RB Tree is 2log(n+1) 2
3 Discuss all the various cases of inserting any element in any RB Tree. 2
4 Explain binary search tree with any one example. 1
5 What are the various AVL tree rotations ? 3
6 Construct RB Tree after inserting elements 41,38,31,12,19,8 5
7 Insert following keys into RB Tree 4,7,12,15,3,5,14,18,16 3
8 Construct RB Tree after inserting keys 40,50,70,30,42,15,20,25,27,26,60,55 5

9 Discuss the various cases of RB Tree deletion. 2

10 Explain RB Tree deletion with the help of any one example. 2

11 Define binomial heap with its various properties and discuss the various cases of 1
binomial heap union with its algorithm.

12 Let A={7,2,4,17,1,11,6,8,15,10,20} 3
(i) Draw a binomial heap whose key elements are elements of A
(ii) Insert a new element with the key 5 into this heap
(iii) To a binomial heap obtained this way apply the operation of extracting
the
node with minimum key two times , after each change in the structure of the
heap draw its current diagram.
13 Prove that maximum degree of any node in an n node binomial heap is logn. 3
14 Discuss Fibonacci heap with its various properties and example. 1
15 Discuss B Tree with its various properties in brief. Show the result of inserting the 3
following keys in an initial empty B-tree of order 5
C,N,G,A,H,E,K,Q,M,F,W,L,T,Z,D,P,R,X,Y,S
16 Explain skip list with its various properties in brief. 1
SUPPLEMENTARY QUESTIONS
1 Derive the time complexity of RB Tree insertion . 5
2 Differentiate between binomial heap and Fibonacci heap. 2

IQAC/ASU/F/2023-24/2.1 Page 1 of 2
 TEXT BOOKS:
Ref. Authors Book Title Publisher/Press Edition &Year of
[ID] Publication
E. Horowitz & Fundamentals of Computer Galgotia
[T1] 2nd Edition, 2008
S Sahni Algorithms Publication
[T2] Corman Introduction to Algorithms MIT Press 3rd Edition,2009
REFERENCE BOOKS:
Ref. Edition &Year of
Authors Book Title Publisher/Press
[ID] Publication
Aho, Hopcraft, The Design and Analysis of Pearson
[R1] Ist Edition, 2002.
Ullman Computer Algorithms Education

REFERENCES

Signature of Faculty:______________ Signature of HOD:_______________

(With Date) (With Date)

IQAC/ASU/F/2023-24/2.1 Page 2 of 2