13

14

a)

b)

a)

b)

A6810 Pages: 4

Perform DFS traversal on the above graph starting from node A. Where
multiple node choices may be available for next travel, choose the next node in
alphabetical order. Classify the edges of the graph into different category.

Write and explain an algorithm to find the optimal parenthesization of matrix
chain product whose sequence of dimension is given.

Write and explain merge sort algorithm using divide and conquer strategy. Also
analyse the complexity.

Write down and explain Bellman Ford algorithm. Will your algorithm detect all
negative cycles in the graph. Justify your answer.

Apply Bellman Ford algorithm on the graph given below. Assume Node | as

source vertex.

PART E

Answer any four full questions, each carries 10 marks.

15 a) Write down Prim’s algorithm and analyse the complexity.

b)

Apply Prim’s algorithm on the graph given below.

டு ज्जी

16 a) Consider the following algorithm to determine whether or not an undirected

graph has a clique of size k. First, generate all subsets of the vertices
containing exactly k vertices. Next, check whether any of the sub-graphs
induced by these subsets is complete (i.e. forms a clique).

Why is this not a polynomial-time algorithm for the clique problem, thereby

Page 3 of 4

(5)

(4)

(5)

(4)

(4)
(6)