This is a closed book exam, but you may use one page of prepared notes. Answer all of the questions.
Describe the main ideas behind greedy algorithms.
What problem does Dijkstra's algorithm solve?
Is the vertex cover problem known to be NP-complete, or is that only conjectured? Is it known whether the vertex cover problem is in the class P? Is it known whether the vertex cover problem is in the class NP?
Do problem 17.2-5.
The partition problem is as follows. You are given a list of positive integers. You would like to create two sublists of the input list, with each number in exactly one of the sublists, so that the sum of the numbers in each sublist is the same. Describe a nondeterministic polynomial time algorithm for the partition problem.
Suppose that A and B are two sets that belong to the class NP. Show that the intersection of A and B is also a member of NP.
The independent set problem is as follows. The input consists of an undirected graph G and a positive integer k. You are asked whether graph G has an independent set of size at least k. An independent set in a graph is a set of vertices that are mutually nonadjacent. That is, none of them are adjacent to any of the other ones. Prove that the vertex cover problem reduces to the independent set problem.