Computer Science 3650
Summer 2004
Practice Questions for Exam 3

This is a closed book exam, but you may use one page of prepared notes. Answer all of the questions.

  1. 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?

  2. What is the definition of the class P?

  3. What is the definition of the class NP?

  4. What is the definition of a polynomial time transformation from A to B?

  5. What is the definition of an NP-complete problem?

  6. 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. For example, if the input list is 2,2,3,4,5,7,9, then you can partition this into (2,2,5,7) and (3,4,9), each with sum 16. Notice that each number in the input list is present in exactly one of the two sublists. If a number is repeated, it must occur the same number of times total in the sublists.

    1. Express the partition problem as a set.

    2. Describe a nondeterministic polynomial time algorithm for the partition problem.

  7. The 0-1 Knapsack Problem is as follows. The input consists of a list of numbers x1,...,xn and a positive integer K. The question is whether there exists an index set I that is a subset of {1,...,n} such that the sum of xj for all j in I is exactly K.

    1. Express the 0-1 Knapsack Problem as a set.

    2. Show that there is a polynomial time transformation from the Partition Problem to the 0-1 Knapsack Problem.

  8. 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.

  9. A simple path in a graph is a path that does not hit any vertex more than once. The Longest Path problem is as follows.

    Input: An undirected graph G and a positive integer K.

    Question: Is there a simple path in G that has length at least K?

    Show that the Hamilton Path problem can be transformed in polynomial time to the Longest Path problem.