0. In the text: (7 points)
Page 142: 9. Pages 331-333: 1, 2, 4 Page 337-338: 1, 4, 7
1. Depth First Search (2 points)
Given a directed graph, with n vertices and e edges, with vertices numbered 1 through n. For every vertex, v, there is a minimum numbered vertex M(v) reachable by some path from v. Design an O(n + e) algorithm to find M(v) for all vertices in the graph. Hint: Reverse the edges of the graph.
2. Dijkstra's Algorithm (2 points)
Explain why Dijkstra's method works for graphs with negative edges (but no negative cycles) if all the negative edges emanate from the source vertex.
3. Practice with Graph Algorithms (6 points)
a. Draw a graph that has negative edges but no negative cycles, for which Dijkstra’s algorithm computes an incorrect shortest path tree.
b. An interval graph is an undirected graph where the nodes are closed intervals on the real number line, and the edges connect intervals that overlap. Draw the depth first search(DFS) tree of the following interval graph: {[1, 3], [2, 4], [6, 9], [5, 10], [8, 9], [8, 11], [3, 6], [1, 4], [3, 7]}. Assume that the graph data structure orders the nodes as they are listed, and you start your search from the first node. Darken all tree edges, and leave back edges light colored.
c. Using the graph on page 337 (2b), draw the shortest path tree constructed by Dijkstra’s algorithm and the breadth first search(BFS) tree constructed by a breadth first search. Start with node a.
4. Shortest Path Algorithm (1 point)
Does the BFS-scanning shortest path algorithm (Bellman-Ford) work on a graph with a negative cost cycle? If yes, prove that it does; otherwise explain what happens and why. Give an example in either case.
5. Topological Sorting (7 points)
Write a program to topologically sort a directed graph by repeatedly finding a vertex of in-degree 0 and deleting it from the graph. Make sure your algorithm runs in at most O(n2) or O(n + e) time. You can use either adjacency lists or an adjacency matrix for the graph data structure. In order to succeed, process the graph initially to calculate an in-degree array for each node. Add any node of in-degree zero to a queue. While the queue is not empty, delete a node from the queue, and update the in-degree array.
Test your program on the following graphs. The input should be read from a file and converted by your program to whatever graph data structure you are using. You can assume
(a)
1 -> 2 -> 3 -> 4
2 -> 3 -> 5
3 -> 4 -> 5
4 -> 5
5 -> .
(b)
{ 0, 1, 0, 0, 0, 0, 0, 0 }
{ 0, 0, 0, 1, 1, 1, 0, 0 }
{ 1, 0, 0, 1, 0, 0, 0, 0 }
{ 0, 0, 0, 0, 0, 0, 1, 0 }
{ 0, 0, 0, 0, 0, 0, 0, 0 }
{ 0, 0, 0, 0, 1, 0, 0, 0 }
{ 0, 0, 0, 0, 0, 0, 0, 1 }
{ 0, 0, 0, 0, 0, 1, 0, 0 }
6. Finding a Cycle in Undirected and Directed Graphs
(4 points)
a. Write an O(n + e) algorithm using DFS that determines whether or not an undirected graph has a cycle. Your algorithm should print the first cycle that it finds. Hint: Use a stack in the DFS algorithm to keep track of the vertices in the order that they are visited, and stop if you ever get a non-tree edge (i.e., a back edge). Be careful to distinguish between a back edge, and a tree edge in the reverse direction.
b. Write an O(n + e) algorithm using DFS that determines whether or not a directed graph has a cycle. For a directed graph, you need not worry about following a tree edge in the wrong direction, because all edges are directed. However, a non-tree edge is not necessarily a back edge. The DFS tree can be stored using a parent array. Explain how to use the parent array of the DFS tree, to detect a back edge in a directed graph, and thereby find a cycle.
7. Depth First Search (8 points)
You are given a graph G where each vertex has an associated label E, B or W. This graph represents a final position in a game where E stands for empty, B for black and W for white. The score for black is the total number of vertices labeled E which are surrounded by B 's. The score for white is the total number of vertices labeled E which are surrounded by W 's. Note that if an empty spot can reach both W and B, then it does not count at all in the score; the point is considered neutral. There are no neutral points in the example below, but your program should consider that possibility. On a board with no B and W stones, the score would be undetermined.
A vertex is surrounded by B if and only if no path starting from it reaches a vertex labeled W, and some path from it eventually reaches a B. A vertex is surrounded by W if and only if no path starting from it reaches a vertex labeled B, and some path from it eventually reaches a W.
a. Write a program that takes in a graph and returns the final score. Your algorithm should run in O(n + e) time, the standard time for a DFS. You should use the standard DFS skeleton wrapped in a loop from 0 to 80, similar to the connected component application we did in class. You will need to add a few lines in the right spots of the skeleton to keep track of the score. Each depth first search should return a score and whether the score is B, W, or N (neutral), or U (undetermined). That is, every DFS call should return an object (int score, char color).
b. Test your program on the following 9 by 9 Go Board. Note that the score here is 20 for Black, and 18 for White. To test neutral points, you should change the upper right corner from empty to white. Then the score would be 3 for Black, and 18 for White. I will give you some other modifications when you demo your program.
This board must be converted to an 81 node graph. The reason for this is that other boards may not be grids, and you want your scoring algorithm to work on any structure. The nodes are positions on the board either Empty, Black, or White. The edges are connections between positions. Every position in the middle of the board is connected to four other positions, to the left, right, above and below. Positions on the edges are connected to only three other positions, the corners only to two. Diagonals are not connected, and the connections do not wrap around the sides of the board.
To store the graph you should use an array of adjacency lists. You should store the color of each node (B, W, or E) in a parallel array to the graph called color[]. So if you number the nodes row by row, right to left from 0 to 80, the graph above should look like:
0 : --> 1 --> 9.
1 : --> 0 --> 2 --> 10.
...
The color[] array should be: B, E, B, E, E, E, ...
Your program should automatically build the graph data structure from the board. The "board" file for the above picture is shown below. For the extra white stone variation, you should change the last E on row 1 to W.
BEBEEEEEE
EBEEBEEEE
BEBBBBEEE
BBBWWBBBE
BBWEEWWBE
WWWEEWBBB
EEEWEWWBB
EWEEEEWWB
EEEEEWWWW
Hints:
1. You should do this with a single DFS, wrapped in a loop from 0 to 80.
local_score = 1; local_color = 'U'; //start undetermined. color can be U( undetermined), B (black), W (white), or N (neutral)
for i = 0 to 80
if unvisited[i] and color[i] is E then {(color, score) = DFS[i]; // add the score returned to the proper color B or W}
2. Each DFS works like this:
DFS(x)
for every y adjacent to x
if color[y] is B or W then process local_color;
if unvisited[y] and color[y] is E then { (color, score) = DFS(y); add score to local_score; update local_color based on color; } // see me if you don't know how
return (local_score, local_color);
8. The Circus Problem (3 points)
Describe an O(n+e) algorithm to solve the
problem below. The data for the problem can be encoded
into a graph in O(n2) time.
You don’t need to code it - but be specific about data
structures and methods. Analyze the time complexity of your
algorithm.
A circus is designing an act consisting of a tower of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below her. Given the number of people in the circus, followed by the heights and weights of each one in inches and pounds respectively, what is the largest possible number of people in such a tower?
Hint: Reduce this to a longest path problem on an acyclic directed graph. Then reduce to a shortest path on an acyclic graph by changing each edge to -1. Note that there may be more than one node with indegree zero, and it is too slow to start a search from each node, so create a new node smaller and lighter than all the nodes that will be a unique indegree zero node.
Example:
Input: 8 (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (66, 120) (68, 110) (70, 100)
Output: The longest tower is length 6 and one such tower includes from top to bottom:
(56,90) (60,95) (65,100) (68,110) (70,150) (75,190)