COS 226 Homework #7
Due: Tuesday, April 19, 2005

Written Exercises

Follow the instructions on the assignments page on how and when to turn these in.  Point values of each problem are shown in brackets.  Be sure to also complete the programming part of this assignment, including the program report.

1. [4]  (CLRS exercise 22.4-1, slightly adapted)  Show the ordering of vertices produced by the topological sort algorithm given in class when it is run on the following DAG:
   
   
   
   Assume that DFS considers vertices in alphabetical order, and that all adjacency lists are also given in alphabetical order.
    
2. [10] (CLRS exercise 22.4-2, slightly adapted)  Give a linear-time algorithm that takes as input a directed acyclic graph G and two vertices s and t, and returns the number of paths from s to t in G.  For example, in the DAG above, there are exactly four paths from vertex p to vertex v:  p-o-v,  p-o-r-y-v,  p-o-s-r-y-v  and  p-s-r-y-v.  (Your algorithm only needs to count the paths, not list them.)
    
3. [4] (CLRS exercise 22.5-2, slightly adapted)  Show how Kosaraju's algorithm works on the following graph:
   
   
   
   Specifically, show the postorder numbering computed in the first phase of the algorithm.  Then show the DFS forest produced in the second phase.  Assume DFS in the first phase considers vertices in alphabetical order and that the adjacency lists are in alphabetical order.
    
4. [4] Give a simple example of a directed graph with negative-weight edges but no negative cycles for which Dijkstra's algorithm produces incorrect answers.  Be sure to demonstrate why Dijkstra's algorithm fails on your example.
    
5. [4] Consider a network defined on five vertices A, B, C, D and E with the following directed edges and edge weights:
   
             B-A   1
             B-C   1
             C-A   5
             C-D   1
             D-A   3
             D-B   1
             E-C   1
             E-D   4
   
   (For instance, the first line represents a directed edge from B to A with edge weight 1.)
   Show how the Bellman-Ford algorithm computes shortest paths on this graph when E is the source vertex.  Use the version of Bellman-Ford given in class which considers all edges on every iteration.  Assume edges are considered in the order given above.  After each iteration, show the value of wt for each vertex.