1. Prove that the problem of finding a Hamilton cycle in a directed graph is Complete, by reduction from the Hamilton-cycle problem for undirected graphs. 2. Suppose that we have an algorithm to solve...

1. Prove that the problem of finding a Hamilton cycle in a directed graph is Complete, by reduction from the Hamilton-cycle problem for undirected graphs.

2. Suppose that we have an algorithm to solve the decision version of boolean satisfiability—for any input it determines whether there exists an assignment of truth values to the variables that satisfies the boolean expression. Show how to use such an algorithm to find the assignment.