CSPP 55001 Algorithms — Autumn 2013

Homework 6 (assigned November 5, due November 12)

Reading: CLRS chapter 22, sections 22.1–22.5. 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.2-8, page 602.

2. Exercises 22.3-10 and 22.3-12, page 612.

3. Exercises 22.4-3 and 22.4-5, page 615.

4. You are given a directed graph G = (V, E) in which every vertex has at least one outgoing edge. Your task is to find a vertex v that is part of a directed cycle.
• Argue that G must contain at least one directed cycle.
• Can you use a single BFS to find such a vertex? If so, how? If not, why not?
• Can you use a single DFS to find such a vertex? If so, how? If not, why not?

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 transpose of a directed graph G = (V, E) is another directed graph GT = (V, ET) on the same vertex set, but with edges reversed, i.e., ET = {(i, j) : (j, i) in E}. Give an O(V + E) time algorithm for computing the transpose of a directed graph G = (V, E) in adjacency list format.
• Describe your algorithm in pseudocode. (5 points)
• Explain how your algorithm works and argue that it is correct. (2 points)
• Analyze the running time of your algorithm, i.e., explain how it achieves its O(V + E) time complexity. (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 format; vertices u and w in V.
Output: The number of distinct shortest paths from u to w.
Note: Your algorithm should not list all the paths; just compute their number.
• Describe your algorithm in pseudocode. (5 points)
• Explain how your algorithm works and argue that it is correct. (2 points)
• Analyze the running time of your algorithm. (1 point)

3. An undirected graph is called bipartite if its vertices can each be assigned a color, either red or blue, such that no red vertex is adjacent to another red vertex, and no blue vertex is adjacent to another blue vertex. Give an efficient algorithm to determine if an undirected graph G = (V, E) is bipartite. Assume that G is in adjacency list format. Your algorithm should work even if G is not connected.
• Describe your algorithm in pseudocode. (5 points)
• Explain how your algorithm works and argue that it is correct. (2 points)
• What is the running time of your algorithm? Explain. (1 point)

4. Two vertices that are far apart in a communication network—separated by many hops—are thought to have a more tenuous connection than two vertices that are close together. There are a number of algorithmic results that are based on different ways of making this notion precise. Here is one that involves the susceptibility of paths to the deletion of vertices.
Suppose that an undirected graph G = (V, E) with |V| = n contains two vertices s and t such that the distance between s and t is strictly greater than n/2. (Recall: the distance between two vertices u and v in a graph G = (V, E) is the minimum number of edges in a path joining them.)
• Show that there must exist some vertex w, not equal to either s or t, such that the graph obtained from G by deleting w contains no path from s to t. (4 points)
• Describe an algorithm with running time O(V + E) to find such a vertex. Describe all the steps of your algorithm in clear and concise English, using pseudocode if it is helpful. (4 points)

5. Suppose the CSPP curriculum consists of n courses, all of them mandatory. The graph G = (V, E) of prerequisites has a vertex for each course, and an edge from course u to course w if and only if u is a prerequisite for w. Give an algorithm that works directly with this graph representation, and computes the minimum number of quarters necessary to complete the curriculum. Assume that a student can take any number of courses in one quarter. The running time of your algorithm should be O(V + E).
• Describe your algorithm in pseudocode. (6 points)
• Explain how your algorithm works and why it is correct. (2 points)
• Analyze the running time of your algorithm. (1 point)

6. Give an O(V + E) time algorithm that takes as input a directed acyclic graph G = (V, E) and two vertices s and t in V, and outputs the number of different simple directed paths from s to t in G. (Your algorithm only needs to count the simple paths, not list them.)
• Describe your algorithm in pseudocode. (6 points)
• Explain how your algorithm works and why it is correct. (2 points)
• Analyze the running time of your algorithm, i.e., explain how it achieves its O(V + E) time complexity. (1 point)