Problem
1. List three problems that have polynomial-time algorithms. Justify your answer.
2. Give a problem and two encoding schemes for its input. Express its performance using your encoding schemes.
3. Show that a graph problem using the number of vertices as the measure of the size of an instance is polynomials equivalent to one using the number of edges as the measure of the size of an instance.