This is a closed book exam, but you may use one page of prepared notes. Answer all of the questions.
Consider the definition
h(0) = 1
h(n) = h(n-1) + h(floor(n/2)) + 1
For example, h(2) = h(1) + h(1) + 1 = 3, h(3) = h(2) + h(1) + 1 = 5, etc.
An obvious algorithm to compute h is a recursive one, based directly on
the defining equations. Is that algorithm efficient? Why or why not?
If not, how can the algorithm be improved?
Justify your answer.
Solution. This is not an efficient algorithm because it duplicates work. Consider computing h(9). That involves computing h(8) and h(4). But computing h(8) will also require computation of h(4), so h(4) is computed more than once. As the recursion gets deeper, the amount of duplicated work goes up greatly.
An improved algorithm uses memoizing. It computes an array h, starting with small indices and working its way up. h[1] is filled in as 1 to start. Each of the remaining entries, up to the desired value, is filled in by fetching two previously computed values.
What are the main principles of dynamic programming algorithms? That is, what characteristics do they share?
Solution. Dynamic programming algorithms share the following characteristics. First, they rely on making decisions by trying different alternatives and selecting the best one. (They do not speculate about which one will be the best.) Handling a choice involves looking at smaller problems of the same kind. As computation proceeds, it can (and usually does) happen that the same subproblem needs to be solved many times. To avoid repeated effort, a dynamic programming algorithm memoizes its results.
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?
Solution. The vertex cover problem is known to be NP-complete. The vertex cover problem is known to be in NP. (There is a nondeterministic polynomial time algorithm to solve it.) If P and NP are different classes, then the vertex cover problem is not in P. However, nobody knows whether P and NP are different; that is only conjectured. So it is only a conjecture that leads to the conclusion that the vertex cover problem is not in P.
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.
Solution.
The certificate is a way to partition the input list into two piles. If there are n values in the list, this is just a matter of providing n bits, each telling whether one of the numbers goes into the first or second pile.
To check the certificate, compute the sum of each pile. If the two sums are the same, then accept the certificate. If not, reject the certificate.
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.
Solution. Since A and B are in NP, there is a nondeterministic algorithm for each of them. That is, every member of A has an easily checked certificate showing that it is in A, and every member of B has an easily checked certificate showing that it is in B. We need to find an easily checked certificate showing that a given value is in both A and B. Just take the certificates for membership in A and membership in B and combine them. So a certificate for membership in A intersected with B has the form (C1,C2), where C1 is a certificate that the given value is in A, and C2 is a certificate that the given value is in B.
To check certificate (C1,C2), check that both certificates are valid. (Of course, C1 is checked using the checking algorithm for A and C2 is checked using the checking algorithm for B.)
By the way: If A is a set of strings then the complement of a set A is the set of all strings that do not belong to A. The same kind argument does not work to show that if A is in NP then the complement of A is also in NP. Can you see why? It is conjectured that, if A is NP-complete, then the complement of A is not in NP.
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.
Solution. If G is a graph with n vertices, let f(G) = (G,n). Then f is a polynomial time transformation from the Hamilton Path problem to the Longest Path problem. f is clearly computable in polynomial time. (You just need to count the vertices in the graph.) Then just notice that G has a Hamilton path if and only if G has a simple path of length n.