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

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


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]


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]


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]


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]


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.


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]


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]


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:


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]


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