Homework 6 (assigned May 8, due May 15)

Reading: CLRS chapter 22, sections 22.1–22.4. Reading for next week's lecture: chapter 24, sections 24.1–24.3.

Written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.
Note: You are responsible for the material covered in both "Do" exercises and assigned problems.
Note: If you work with others, indicate their names at the top of your homework paper. Everyone must submit their own independently written solutions.

"Do" Exercises (not to be handed in):

1. Exercise 22.1-3, page 592.

2. Exercise 22.2-9, page 602.

Assigned Problems (to be handed in):

Important: When describing an algorithm in pseudocode, explain the meaning of your variables in English. Comment the lines of your pseudocode. Your pseudocode should be short, clear, and complete to receive full credit. If your code is long, difficult to read, or incomplete, you will not receive full credit.

1. The vertex-coloring problem seeks to assign a color to each vertex of a graph such that no edge links any two vertices of the same color. This problem can be solved by assigning each vertex a unique color. However, the goal is to use as few colors as possible. An undirected graph G = (V, E) is bipartite, or 2-colorable, if it can be colored so that adjacent vertices have different colors, using only two colors. Given an undirected graph G = (V, E) in adjacency list representation, determine if G is 2-colorable in O(V + E) time. If G is 2-colorable, then your algorithm should construct a valid 2-coloring of G within O(V + E) time. Hint: modify BFS. Your algorithm should work even if the input graph G is not connected.
   • Describe your algorithm in pseudocode. (5 points)
   • Argue that your algorithm is correct. (1 point)
   • Analyze the running time of your algorithm. (1 point)

2. Often there are multiple shortest paths between two vertices in a graph. Give an O(V + E) time algorithm for the following task.
   Input: An undirected graph G = (V, E) in adjacency list representation; vertices u and w in V.
   Output: The number of distinct shortest paths from u to w.
   • Describe your algorithm in pseudocode. (5 points)
   • Explain how your algorithm works and argue that it is correct. (1 points)
   • Analyze the running time of your algorithm. (1 point)
   Note: Your algorithm should not list all the paths; just compute their number.

3. Given an undirected graph G = (V, E) in adjacency list representation, give an algorithm that determines whether or not G contains a simple cycle, i.e., a path of the form v₀, v₁, …, v_k where k ≥ 3, v₀ = v_k, and the vertices v₀, v₁, …, v_{k − 1} are distinct. Your algorithm should run in O(V) time, independent of |E|.
   • Describe your algorithm in pseudocode. (5 points)
   • Explain how your algorithm works and why it is correct. (1 points)
   • Analyze the running time of your algorithm; explain how it achieves its O(V) time complexity. (1 points)

4. A vertex cover of a graph G = (V, E) is a subset of vertices S ⊆ V that includes at least one endpoint of every edge in E. 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.
   Your algorithm should run in O(n) time, where n is the number of vertices.
   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}.

   
   • Define the subproblem to be solved. (4 points)
   • State the recurrence that expresses the optimal solution of the subproblem in terms of optimal solutions of smaller subproblems. (5 points)
   • Describe your algorithm in pseudocode. (4 points)
   • Analyze the running time of your algorithm. (1 point)