Algorithms and Data
Spring 2010

Due date: February 10, 2010
At beginning of lecture


Problem 4.1:

Solve problem 4.20 from Kleinberg/Tardos.

Problem 4.2:

Implement an O(m+n) topological sorting algorithm in your
favorite programming language. 
m is the number of edges and n the number of nodes.

You design your own input format based on adjacency lists.
Using constructor calls to create the DAGs is probably easiest because you don't need a parser.
The output consists of the topologically sorted nodes.
Print an error message if you find a cycle.

Argue why your implementation is O(m+n).