10

11

12

13

14

b)

a)

b)

a)

b)

a)

03000CS302052001

for (j=1;jprintf("%d" ,i+j);
}

}

Find the time complexity of check in terms of 6 — notation.
Find the minimum and maximum height of any AVL-tree with 1186068.

Assume that height of the root is 0.

PART C
Answer all questions, each carries3 marks.
What is principle of optimality?
Explain the characteristics of problems that can be solved using dynamic
programming.

Find the possible topological orderings for the following graph

How the edges of a graph can be classified based on DFS?

PART D

Answer any two full questions, each carries9 marks.
Give a control abstraction for Divide and Conquer method. Explain with an
example.
Explain the effect of negative weight edges and negative weight cycles on
shortest paths.
Define strongly connected components. How DFS can be used to find strongly
connected components?
Find an optimal paranthesizationof a matrix-chain product whose sequence of
dimensions is 4x 10,10x3,3x 12,12x20,20x7.
Write Dijkstra’s Single Source Shortest path algorithm. Analyse the complexity.

Page 2 of 3

(5)

(3)
(3)

(3)

(3)

(5)

(4)

(4)

(5)

(7)