Search & Filtering
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)
- A hospital wants a program that records and monitors the temperature of each baby that is currently in its maternity unit. It wants to store the temperature of each baby; it will have 15 babies in the unit at a time.
- If a baby’s temperature is below 36.5 degrees, the program should alert a nurse with a suitable message.
- If a baby’s temperature is above 37.5 degrees, the program should alert a nurse with a suitable message.
Write an algorithm that the hospital could use to store and monitor the temperatures of the babies in the unit. [6]
