15

16

17

18

19

20

D7420

Module IV
If we are given a directed graph G with n vertices. Explain how will you find out (6) the

length of the shortest path between any pair of vertices in G. Justify your answer with an
example.
OR
What is dynamic programming? Explain how this concept is applied to solve (6) travelling
salesman problem.
Module V
Explain how N- queen’s problem is solved using the concept of backtracking. (6)
OR
Explain N-1 puzzle problem in detail. (6)
Module VI
a) Explain NP-Hard and HP-complete classes. (3) b) Explain Clique problem. (3)
OR

Prove that the travelling sales person problem is NP-complete. (6) ****

Page 2 of 2