# RTU Previous Year Question Papers BE CSE Fifth Semester

# Advanced Data Structure Dec 2011

**UNIT-I**

1. a) State the condition under which insertion of a vertex in a Red-Black tree will result in a sequence of recolouring steps that terminate with the root changing colour.

b) Will the root of Red-Black tree always be black after performing a deletion operation ? Justify with an example.

**OR**

1 (a) Construct a 2-3 tree for the list 9, 5, 8, 3, 2, 4 and by successive insertion.

(b) Define Dictionary and Dictionary with duplicates. List the operation performed on dictionary.

**UNIT-II**

2 (a) Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3,and 9. One at a time into an initially empty min heap ?

(b) Explain the implementation of a binomial heap and its operation with suitable example.

**OR**

2 Write short note on :

(a) Binomial trees

(b) Implementing fibonancy heap

**UNIT-III**

3 A network G = (V,E) as follows

V = {a, b, c, d, e, f}

E = {(ab, 2), (Cb, 2), (Cd, 2), (ed, 2), (ef, 2), (ac, 4), (be,

4), (df, 4) }

where the number following each edge is the capacity of that edge :

(i) A function f is defined on the edge of G with each edge e having f (e) equal to the capacity of e. Explain why this defines a valid st. flow on G for suitably chosen vertices S and t.

(ii) State the Max-flow Min-cut theorem and explain how your answer to part (a) illustrate this theorem.

**OR**

3. Consider the following graph :

(a) Apply ItruskaTs algorithm to G. List the edge of the forest that is grown, in the order that they added.

(b) What is the weight of minimum spauing tree in G ?

**UNIT-IV**

(a) What- if zero-one principle ? Describe in detail.

(b)Prof that if a comparison network with n input sorts aB 2^{n} bmary string of length n correctly, then it sort all sequence correctly.

**OR**

(a) Explain the bitonic sorting network with suitable

(b) Write short note on :

(i) Ftirity Queue

(ii) Operations on disjoint sets.

**UNIT – V**

5 (a) Describe the Chinese remainder theorem.

(b) What ftvisien theorem ? Explain.

**Or**

5 Write note on :

(a) Computation of Discrete logarithm

(b) Modular Arithmetic