CS502 Fall 2011 Final Term Feb 2012 – VU Current Paper – 12 Feb 2012

total marks 80
mcqs 40
4 questions of 2 marks
4 questions of 3 marks
4 questions of 5 marks

60% paper from graphs

How we convert the shortest path problem into a single source problem? 2 Marks
If problem A reduces (is polynomial-time reducible) to problem B and B is NP-complete then A is NP-complete
Consider the following code:
For(j=1; j f[v]. If this edge is a back edge, then f[u] _ f[v] 3 marks
Where the Clique Cover Problem arises 3 marks
What is decision problem, also explain with example? 2 marks
How Dijkstra’s algorithm operates? 3
write suedo code of relaxing a vertex 5
Explain why the statement “The running time of A is at least On2 ” is meaning less 5 Marks
Show the strongly connected components of the following graph using DFS algorithm. Take node E as a starting node. 5 marks