7

10

11

13

14

a)

b)

a)

b)

a)

b)

03000CS302052102

Construct a Red Black tree by inserting 10, 20, 30, 15, 16 and 27 into an initially
empty tree.

What do you mean by asymptotic growth rate? Define Big Oh, Big Omega and
Theta notion.

PART C
Answer all questions, each carries 3 marks.

Define spanning tree of a graph. Write the total number of spanning trees
possible for a complete graph with 4 vertices.

Write the algorithm to find Strongly Connected Components in a graph.
Explain Divide and Conquer strategy with example.

What are the characteristics required by problems so that they can be solved by
dynamic programming approach?

PART D
Answer any two full questions, each carries 9 marks.
Apply these algorithms on the following graph. Let A be the source vertex.

Analyse complexity of each algorithm.

1) BFS 5

(^
(०) (">
ಮ್ನ ‏سے‎

ಕ್ರಾ

ಕಾ
‏کے‎

ری
‎Write down and explain Bellman Ford algorithm. Will your algorithm detect all‏
‎negative cycles in the graph? Justify your answer.‏
‎Explain Strassen’s matrix multiplication with example and analyse its‏
‎complexity.‏
‎Write Dijkstra’s Single Source Shortest path algorithm and illustrate with‏

example.

Write an algorithm to merge 2 sorted arrays into a single sorted array.

Page 2 of 3

(5)

(4)

(3)

(3)
(3)
(3)

(9)

(4)

(5)

(5)

(4)