Homework 8 (assigned May 21, due May 27)

Reading: CLRS section 22.3; chapter 23; section 24.3

Written assignment: Solve the following exercises and problems. Turn in only the problem solutions. Please note: You are responsible for the material covered in both exercises and problems.

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

In the following exercises assume that adjacency lists are given as singly-linked lists.
1. Exercise 22.1-3 on CLRS page 530.
2. Given a directed graph G = (V, E) in adjacency list representation, describe an O(V+E) time algorithm that arranges the members of each adjacency list in increasing order.
3. Given a directed graph G = (V, E) in adjacency list representation, describe an O(V+E) time algorithm that determines if the graph is undirected. A directed graph is undirected if whenever an edge (i, j) belongs to E, its reverse (j, i) also belongs to E.

Problems (to be handed in):

1. Basic graph searching
   Exercise 22.2-1 on CLRS page 538. Show the traversal's queue and construct the corresponding BFS tree. (5 points)

2. Connected components
   An undirected graph is connected if there is a path from u to v for every pair of its vertices u and v. If an undirected graph is not connected, it will consist of several connected pieces that are called connected components of the graph. Formally, a connected component is a maximal (not expandable by inclusion of an extra vertex) connected subgraph of a given undirected graph. For example, the graph of Figure B.2.b (CLRS page 1081) is not connected because, for instance, there is no path from vertex 1 to vertex 3. This graph has three connected components with vertices {1, 2, 5}, {3, 6}, and {4}, respectively.
   1. Explain how one can identify the connected components of an undirected graph G = (V, E) in O(V+E) time using BFS. (5 points)
   2. Modify the BFS pseudocode on CLRS page 532 to identify the connected components of an undirected graph G = (V, E) in O(V+E) time. (10 points)

3. Bipartite testing
   A bipartite graph is an undirected graph G = (V, E) whose vertices can be partitioned into two disjoint subsets V₁ and V₂ (i.e., V = V₁ ∪ V₂ and V₁ ∩ V₂ = ∅) such that there are no edges between vertices in the same set. For instance, if u and v are in V₁, then there is no edge between u and v. One can also say that an undirected graph is bipartite if its vertices can be colored in two colors so that every edge has its vertices colored in different colors; such graphs are also called 2-colorable.
   1. Design a BFS-based algorithm to determine whether an undirected graph G = (V, E) is bipartite and write pseudocode for your algorithm. For full credit your algorithm should run in O(V + E) time. (15 points)
   2. Explain briefly why your algorithm is correct. (Note: your algorithm should work even if G is not connected.) (5 points)

4. Multiple shortest paths
   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) with unit edge weights; vertices u and v in V.
           Output: The number of distinct shortest paths from u to v.
   (Note: your algorithm should not list all the paths; just compute their number.) (20 points)
   Hint: Modify BFS.

5. Shortest path counting
   A chess rook can move horizontally or vertically to any square in the same row or in the same column of a chessboard. Write a dynamic programming algorithm to find the number of shortest paths by which a rook can move from one corner of a chessboard to the diagonally opposite corner. (20 points)