0.  In the text:  Page 557:  22.5-2.  Page 559:  22-4.  Page 575-578:  23-1, 23-4.  Page 591:  24.1-1.  Page 600:  24.3-1, 24.3-8.

1.  Practice with Graph Algorithms

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 with all tree edges, and back edges 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.
c. Using the graph on page 562, 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.

2.  Shortest Path Algorithm

Does the BFS-scanning shortest path algorithm (similar to 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.

3.  Toplogical Sorting

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(n²) time.

4.  Finding a Cycle in an Undirected Graph

Write an algorithm using DFS that determines whether or not an undirected graph has a cycle.  Your algorithm should print the first cycle that it finds.  Analyze the time complexity of your algorithm.  (Note that although the previous problem can be used to detect whether a cycle exists, it does not identify the cycle).  Hint: Use a stack in the DFS algorithm to keep track of the vertices in the order that they are visited. Be careful to distinguish between a back edge, and a tree edge in the reverse direction.

5.  Depth First Search

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.

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.
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.

This board must be converted to an 81 node graph.  You should use a standard graph data stsructure, either a 2-dim array or an array of adjacency lists.  The nodes are positions on the board either Empty, Black, or White.  The edges are connections between positions.  Every position on 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.  Ignore the two X's on the bottom.  You can/should have your program automatically build the graph data structure from the board.  Otherwise, you would have to enter 81 adjacency lists, or an 81x81 adjacency matrix by hand.  The board file for the above picture is:

BEBEEEEEE
EBEEBEEEE
BEBBBBEEE
BBBWWBBBE
BBWEEWWBE
WWWEEWBBB
EEEWEWWBB
EWEEEEWWB
EEEEEWWWW

The 2-dimensional array graph constructed from this would be an 81x81 array.

6. The Circus Problem

Describe an algorithm to solve the problem below.  You don’t need to code it - but be specific about data structures and procedures.

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 heights and weights of each person in the circus, what is the largest possible number of people in such a tower?

Example:

Input: 6  65 100  70 150  56 90  75 190  60 95  68 110
Output:  The longest tower is length 6 and includes from top to bottom:
  56,90 60,95 65,100   68,110   70,150   75,190