Homework 7 (assigned November 10, due November 16)

Reading: CLRS chapter 22; chapter 24, section 24.3. Reading for next week's lecture: chapter 23; chapter 24, section 24.1.

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.3-10 on page 612.

2. Run the DFS-based topological sort algorithm on the following graph. Whenever you have a choice of vertices to explore, pick the one that is alphabetically first.
   
   • Indicate the discovery and finishing times of each vertex.
   • What are the sources and sinks of the graph?
   • What topological ordering is found by the algorithm?
   • What are the other valid topological orderings of this graph? List them.

3. Exercise 22.4-2 on page 614.

4. Run Dijkstra's algorithm on the following graph, starting with vertex A.
   
   • Draw tables showing the intermediate distance values d[v] and parent values π[v] of all the vertices at each iteration of the algorithm.
   • Show the final shortest-paths tree.

5. Exercise 24.3-2 on page 663. Give a graph with a single negative edge and no negative-weight cycles. Omit the question regarding Theorem 24.6.

6. Exercise 24.3-10 on page 664.

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.
Note: DFS, topological sorting, and Dijkstra's algorithm are your main tools for the assigned problems.

1. Given an undirected graph G = (V, E) in adjacency list representation, determines whether G contains a cycle. Your algorithm should run in O(V) time, independent of |E|. No points will be given for algorithms that are not O(V).
   • Describe your algorithm in pseudocode. (10 points)
   • Analyze your algorithm; explain briefly how it achieves O(V) time complexity. (3 points)
   • Argue that your algorithm is correct, i.e., explain briefly how your algorithm works. Give an example to clarify your algorithm. (3 points)

2. In class we described an alternative algorithm for performing topological sorting on a directed acyclic graph G = (V, E): repeatedly find a vertex of in-degree 0 (no incoming edges), output it, and delete it and all of its outgoing edges from the graph. This will eventually produce a topological ordering of G, provided that the input graph G in fact is a DAG.
   • Give an algorithm that implements this idea in O(V + E) time. Describe your algorithm in pseudocode. How does your algorithm keep track of the vertices that are eligible for deletion? (10 points)
   • Carefully analyze your algorithm and justify its O(V + E) time. (2 points)
   • Explain how to extend your algorithm so that, given an arbitrariy input directed graph G = (V, E) that may or may not be a DAG, it outputs one of two things: (1) a topological ordering, establishing that G is a DAG; (2) a cycle in G, establishing that G is not a DAG. The running time of your modified algorithm should be O(V + E). (3 points)

3. In cases where there are several different shortest paths between two vertices (and the edges have varying lengths), the most convenient of these paths is often the path with fewest edges. For instance, if vertices represent cities and edge weights represent the costs of flying between cities, there might be several ways to travel from city s to city t which all have the same cost. The most convenient of these alternatives is the one that involves the fewest stopovers. Accordingly, for a specific starting vertex s, we define:
   best[u] = minimum number of edges in a shortest path from s to u.
   In the example below, the best values for vertices S, A, B, C, D, E, F are 0, 1, 1, 1, 2, 2, 3, respectively. Give an efficient algorithm for the following problem:
   Input: Graph G = (V, E); edge weights w(e) ≥ 0; starting vertex s in V.
   Output: The values of best[u] for every vertex u in V.
   • Describe your algorithm in pseudocode. (10 points)
   • Argue that your algorithm is correct, i.e., explain briefly how it solves the stated problem and give an example to show how your algorithm works. (2 points)

4. Consider a road map represented as a weighted undirected graph G = (V, E, w) with positive edge weights where edges represent roads connecting cities in G. Some roads are known to be congested, and while traveling from city s to city t we never want to take a route that takes more than one congested road. We define a Boolean function c[e] for each edge e which indicates whether e is congested or not. Give an efficient algorithm to compute the shortest distance between two cities s and t that does not traverse more than one congested road.
   • Describe your algorithm in pseudocode. (10 points)
   • Argue that your algorithm is correct, i.e., explain briefly how it solves the problem and give an example to show how your algorithm works. (2 points)
   • Analyze the running time of your algorithm. Indicate what data structure(s) you use and how the data structure(s) affect the running time of your algorithm. (3 points)

5. Definition. Let G = (V, E) be a connected, undirected graph. An articulation point of G is a vertex whose removal disconnects G. A bridge of G is an edge whose removal disconnects G.
   • Identify the articulation vertices and bridges of the following graph. (2 points)
     

   • Let G = (V, E) be a connected, undirected graph. Must every bridge e of G be an edge in a DFS tree of G? Give a proof or a counterexample. (5 points)
   • In class we showed that the root of a DFS tree is an articulation vertex if and only if it has more than one child in the DFS tree. Argue that a nonroot vertex v of the DFS tree is an articulation vertex if and only if it has a child y none of whose descendants (including itself) has a back edge to an ancestor x of v. (5 points)
   Cf. Problem 22-2 on page 621 on articulation points and bridges, and the related concept of biconnected component.