A

6 a)

7 2)
b)

8

9

10

11

12 a)
0)
௦)

17192010

Construct a Red Black tree by inserting

Pages:4

10,20,30,15,16 and 27 into an initially

empty tree and also delete 15,16 and 30 from the tree

Solve using Masters theorem
i) T(n)=2T(n/4)+Vn
ii) T(n)=7T(n/2)+ 72

Explain AVL rotations with examples

PART

(0

Answer all questions, each carries3 marks.

Define spanning tree of a graph. Write the total number of spanning trees possible

for a complete graph with 6 vertices.

Write the applications of BFS and DFS

List and explain the characteristic properties associated with a problem that can be

solved using dynamic programming.

Explain Divide and Conquer strategy.

PART

D

Answer any two full questions, each carries9 marks.
What are different classification of edges that can be encountered during DFS

operation and how it is classified? Explain with example

Find strongly connected components of the digraph using the algorithm showing

each step

மு ௩

Write the topological sorting for the DAG given below

Page 2 of 4

(9)

(5)

(4)

(3)

(3)
(3)

(3)

(4)

(3)