1. Show that 3-SAT problem is in NP appealing to the definition of the NP class .
2. Finding a vertex cover of a graph, is a problem of finding a set of vertices of minimum size such that each edge in the graph is covered with at least one vertex. Formulate a decision version of the vertex cover problem.
3. Suppose A and B are two different decision problems and furthermore assume that problem A is polynomial-time reducible to problem B. If problem B is NP-complete, is problem A NP-complete ? Justify your answer.
Q2: As we know, the heuristic or approximation algorithms may not give an optimum solution to the problem but they are polynomial efficient.
(a) Propose an approximation algorithm for travelling salesman problem (TSP) and discuss about its time complexity and limitation. (6 marks)
(b) Give two example inputs, in which the algorithm in (a) gives the best and not-thebest solutions, respectively. The number of nodes should be between six and eight. (4 marks)
Write an algorithm that the hospital could use to store and monitor the temperatures of the babies in the unit.