Notes:

• For this class is is generally not necessary to validate input in your pseudocode: if a problem says the input will be in a certain form then write your pseudocode under the assumption that the input is in that form.
• "Find/devise/give an efficient algorithm" means "find an algorithm that is as efficient as possible, and you have to figure out for yourself whether your solution can be improved."

Problem : Show that $3-SAT \le_P VERTEX\_COVER$ by showing how to, given a 3-CNF formula $\phi$, construct a graph $G$ and pick an integer $k$ so that $\phi$ has a satisfying assignment if and only if $G$ has a vertex cover of size at most $k$. (For your own benefit, prove that your $G$ and $k$ have that property.)

Problem : HAMILTONIAN-PATH (HP: the problem of, given an undirected graph $G$, determining whether $G$ has a Hamiltonian path) is NP-complete. But perhaps the problem becomes easier if we give ourselves a little wiggle room. Consider APPROX-HP, which is the problem of, given an undirected, connected graph $G$, determining if $G$ has a path that visits $n-1$ vertices exactly once and the other vertex at least once, but traverses no edge more than once. Prove that this modified problem is not in fact any easier: APPROX-HP is NP-complete (here we do want the proof that whatever construction you come up with does in fact work).

Problem : FIND-HAMILTONIAN-PATH (FHP) is the problem of, given an undirected graph $G$, returning a Hamiltonian path in $G$, or nil if no such path exists. Prove that FHP and HP are in some sense equivalently difficult: there is a polynomial time algorithm for FHP if and only if there is a polynomial time algorithm for HP. Prove this by showing a) that $HP \le_P FHP$; b) $FHP \le_P HP$ by writing a polynomial-time algorithm for $FHP$ that uses a solution to $HP$ as a subroutine (counting a use of that subroutine as 1 step); and c) that your algorithm for (b) is correct by writing the invariant for it.