Question Paper Details:

University: Rajasthan Technical University

Course: B.Tech Computer science & engineering

Subject: Advanced Data Structor

Exam Year: Dec 2010 / January 2011

Year or Semester: Third year/ Fifth Semester

Paper Code: 5E3166

Unit-I

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.

#### About The Author

Bharat Kumar Dhaker Founder and Editor of ComputerSciencearticle.in, He is an Engineering[Computer Science] Student From Rajasthan. He has a knowledge of C, C++, Java, Adv. Java, HTML and little bit knowledge of PHP.