CS 163 / CS 265 Homework 2,  due Friday, January 25


1. Write pseudocode for
(a) verifying that a supposed topological ordering of a directed graph really is a topological ordering, and
(b) verifying that a supposed directed cycle in a graph really is a directed cycle.
In both cases your pseudocode should take as input a sequence of vertices (that you can loop through, but do nothing else that you do not include in your pseudocode) and a directed graph (in an adjacency list representation).

2. The following pseudocode finds the transitive closure of a given directed acyclic graph (represented as a dictionary mapping each vertex to the set of other vertices it can reach) in a linear number of set operations. The vertical bar ("|") operation is a shorthand for the operation of taking the union of two sets. Why isn't this a linear time algorithm?

reachablefrom = {}        // new dictionary object with no keys or values yet
for each vertex v in the reverse of a topological ordering for G:
    reachablefrom[v] = {v}    // new set object containing only v itself
    for each edge v->w:
        reachablefrom[v] = reachablefrom[v] | reachablefrom[w]

3. If G is a directed acyclic graph without any redundant edges (it is its own transitive reduction), and we perform the layered drawing algorithm described in http://en.wikipedia.org/wiki/Layered_graph_drawing on G, is it always possible to do the layer assignment step in such a way that we don't need any dummy vertices (that is, so that every edge goes between consecutive layers)? For this problem, there is no limit on the number of vertices per layer. If the answer is yes, explain why. If the answer is no, find a counterexample.

4* (CS265 students only). Write pseudocode for an algorithm that computes the transitive reduction of a given directed acyclic graph using only a linear number of set operations (you may use the same output representation as question 2).