< University of Chicago CSPP 55001 Autumn 2013 CSPP 55001 Algorithms — Autumn 2013

Homework 7 (assigned November 12, revised November 16; due November 19)

Reading: CLRS chapter 22, section 22.5; 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. An input directed graph G = (V, E) is given by an array of n vertices and an array of m edges. We assume that the vertices are labeled 1 through n. (This is called the edge-list representation of G.) Write pseudocode to turn the edge-list representation of G into an adjacency list representation in O(V + E) time. Copying an integer between 1 and n counts as one time step.

2. Given a directed graph G = (V, E) in adjacency list format, write pseudocode to construct a monotone adjacency list representation for G in O(V + E) time. Monotone means that the vertices in each adjacency list must be listed in increasing order.

3. Exercises 22.5-3 and 22.5-5, page 620.

4. Exercises 24.3-6, 24.3-8, and 24.3-9, pages 663–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: You may assume that an abstract data structure min-priority queue with operations insert, delete, and decrease-key is readily available to you.

1. Recall that Dijkstra's single-source shortest paths algorithm works correctly when all edge weights are nonnegative.
• Give an example of a weighted directed graph with a single negative-weight edge (but no negative-weight cycle) for which Dijkstra's algorithm gives incorrect answers to the single-source shortest paths problem. Explain how Dijkstra's algorithm fails on your example: what is the shortest-path weight calculated by Dijkstra's algorithm; what is the correct value? (2 points)
• Suppose that we are given a weighted, directed graph G = (V, E) with a single negative-weight edge and that this edge is an outgoing edge from the source vertex s. All other edge weights are nonnegative, and there are no negative-weight cycles. Does Dijkstra's algorithm, started at s, give correct answers to the single-source shortest paths problem for this graph? If yes, prove your answer. If no, give a counterexample. (3 points)
• Suppose that we are given a weighted, directed graph G = (V, E) with a single negative-weight edge not necessarily outgoing from the source vertex s. All other edge weights are nonnegative, and there are no negative-weight cycles. Give an algorithm to compute single-source shortest paths from the given source vertex s to all vertices v in G. Use Dijkstra's algorithm as a subroutine. Note any assumptions on data structures used in your algorithm. Your algorithm should be as efficient as possible.
• Describe your algorithm in pseudocode. (5 points)
• Argue that your algorithm is correct. (2 points)
• Analyze the running time of your algorithm. (1 point)

2. A directed graph G = (V, E) is said to be semiconnected if, for every two vertices u and vV, either there is a path from u to v or there is a path from v to u. Give an efficient algorithm to determine whether or not G, given in adjacency list format, is semiconnected. Maximum points will be given to most efficient algorithms; O(V + E) time is possible. Note: G is not weighted.
• Describe your algorithm in pseudocode. (7 points)
• Explain in clear and concise English how your algorithm works. Argue that your algorithm is correct. (2 points)
• Analyze the running time of your algorithm. (1 point)

3. Given a directed graph G = (V, E) in adjacency list format, give an O(V + E) time algorithm to find an odd-length cycle in G, if one exists. (Hint: first solve the problem assuming that G is strongly connected.) Note: G is not weighted.
• Describe your algorithm in pseudocode. (7 points)
• Explain in clear and concise English how your algorithm works. Argue that your algorithm is correct. (2 points)
• Analyze the running time of your algorithm. (1 point)

4. In cases where there are several different shortest paths between two vertices (and the edges have varying weights), 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. Give an efficient algorithm for the following task.
Input: Graph G = (V, E); positive edge weights w(e) > 0; starting vertex sV.
Output: The minimum number of edges in a shortest path from s to u, for all vertices uV.
• Describe your algorithm in pseudocode. Note any assumptions on data structures used in your algorithm. (7 points)
• Explain in clear and concise English how your algorithm works. Argue that your algorithm is correct. (2 points)
• Analyze the running time of your algorithm. (1 point)

5. You are given a strongly connected directed graph G = (V, E) with positive edge weights along with a particular vertex v0. Give an efficient algorithm for finding shortest paths between all pairs of vertices, with the one restiction that these paths must all pass through v0.
• Describe your algorithm in pseudocode. (7 points)
• Explain in clear and concise English how your algorithm works. Argue that your algorithm is correct. (2 points)
• Analyze the running time of your algorithm. (1 point)

6. To get in shape, you have decided to start running to work. You want a route that goes entirely uphill and then entirely downhill. Your run will start at home and end at work and you have a map detailing the roads with m road segments and n intersections. A road segment consists of a source and a destination intersection and is marked as uphill or downhill. You can assume you have the analog of an adjacency list representation of the map. So you have an array of the n intersections, and for each intersection there is a linked list of the road segments from that intersection with each road segment marked uphill or downhill. Each road segment has a positive length, and each intersection has a distinct elevation.
Assuming the every road segment is either uphill or downhill, give an efficient algorithm to find the shortest route which starts at home, only goes uphill, and then only goes downhill, and finishes at work. State any assumptions made regarding data structures used by your algorithm. Your algorithm should be as efficient as possible.
• Describe your algorithm in pseudocode. (8 points)
• Explain in clear and concise English how your algorithm works. Argue that your algorithm is correct. (2 points)
• Analyze the running time of your algorithm. (1 point)
Give an efficient algorithm to solve the problem if some roads may be level (i.e., both intersections at the end of the road segment are at the same elevation) and therefore can be taken at any point.
• Describe your algorithm in pseudocode. You may just indicate modifications to the code for the previous part. (5 points)
• Analyze the running time of your algorithm. (1 point)