CS 146: Homework due 4/17
Problems from our textbook:
- 22.4-1
- For the same graph as above, run the other topological sort
algorithm we saw in class. To remind you: the algorithm first
calculates the in-degrees of all vertices as the number of
"preconditions" for each vertex. Next, enqueue all
vertices of in-degree 0. While the queue is not empty, dequeues
the next item from the queue, and decrement the number of
preconditions of the vertices the current vertex has an outgoing edge
to. If that number becomes 0, enqueue the appropriate vertex. The
order of vertices into/out of the queue is the topological ordering.
(Note, this method is not given in the book, but is outlined in
problem 22.4-5. We covered it in class.)
- 22.4-2 (think before answering)
- 22.4-3
- 22.5-2
- 22.5-3
- 22.5-7