# 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 2n 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