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.
What are the main principles of dynamic programming algorithms? That is, what characteristics do they share?
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?
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.
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.