2011 Rajasthan Technical University B.Tech 5 (Back) Semester Computer science & engineering "Advanced Data Structor " question paper

1. a) Draw the order-7 B-Tree resulting from inserting the following keys into an initially empty tree T:
4, 40, 23, 52, 11, 34, 62, 78, 66, 22, 90, 59, 25, 72, 64, 77, 39, 12.                       [Marks 10]
b) Write Pseudo code for Right Rotate in Red Black tree. [Marks 6]

OR

a) Discuss union find problem for implementation of disjoint sets. [Marks 8]
b) Explain concatenable queues using 2-3 trees with an example. [Marks 8]

Unit-II

2. a) What is Amortization analysis? Find the amortized cost of ENQUEUE and DEQUEUE operation in Queue. [Marks 8]
b) Describe a concrete implementation of mergable heap ADT that achieves O(log n) performance for all its operation. [Marks 8]

OR

a) Describe comparison network with the help of an example. [Marks 8]
b) Use the zero one principle to prove that the comparison network show in figure below, is a sorting network.  [Marks 8]

Unit-III

3. Write short note (any four):            [Marks 4*4]
a) Isomorphic components
b) Spanning Tree
c) Cut set and cut vertices
d) Fundamental circuits
e) Kuratovski’s two graph.

OR

Draw a simple, connected, undirected, weighted graph with 8 vertices and 16 edges, each with unique edge weights. Illustrate the execution of Kruskal’s algorithm on this graph. [Marks 16]

Unit-IV

4. a) Explain depth first search with an example and write algorithm of depth first search. [Marks 8]
b) Describe strongly connected components and show how the procedure strongly connected components works on the following graph:     [Marks 8]

OR

Answer the following questions:-
a) What is flow network and cuts.
b) What is residual capacity and Augmenting path.
c) Illustrate the execution of ford fulkerson algorithm in the following flow network:

Unit-V

5. a) Explain Euclid GCD algorithm and show the execution of method Euclid GCD (14300, 5915). [Marks 8]
b) What is public key cryptosystem? Describe briefly RSA cryptosystem with example. [Marks 8]

OR

Write short note (any four):      [Marks 4*4]
a) Chinese remainder theorem
b) Division theorem
c) Modular Arithmetic
d) Integer Factorization
e) Primality testing.