Dynamic programming practice problems

1. Problem 15-3 on page 405.

2. Problem 15-10 on page 410.

3. A vertex cover of an undirected graph G = (V, E) is a subset of vertices S ⊆ V such that if (u, v) is in E, then u is in S or v is in S (or both), i.e., S includes at least one endpoint of every edge in E. The size of a vertex cover is the number of vertices in it. The vertex cover problem is to find a vertex cover of minimum size in a given graph. The vertex cover problem is NP-complete. However, vertex cover can be solved efficiently on trees.
   Give a dynamic programming algorithm for the following task.
   Input: An undirected tree T = (V, E).
   Output: The size of the smallest vertex cover of T.
   Example. In the following tree, possible vertex covers include {A, B, C, D, E, F, G} and {A, C, D, F} but not {C, E, F}. The smallest vertex cover has size 3: {B, E, G}.
   Your algorithm should run in O(n) time, where n is the number of vertices in V.