Computer Science 3650
Summer 2003
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. 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.

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

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

5. Show the Knuth/Morris/Pratt prefix function for pattern aabaabcab.

6. The period of a string x₁...x_n is the smallest k > 0 such that x₁...x_n-k+1 = x_k...x_n. That is, removing the first k characters yields the same string as removing the last k characters. For example, the period of string abcabcab is 3, since you get abcab both by removing the first 3 characters and by removing the last three characters. (A string with period k is a prefix of a longer string that consists of the same k-character string repeated over and over.) Every string has a period. For example, the period of abc is 3, since you get the same string (the empty string) by removing the first 3 characters and by removing the last 3 characters.

   Describe an algorithm to compute the period of a length n string that runs in time O(n).