Activity Sheet 6

Manager

name:

Recorder

name:

Speaker

name:

Section 4.2

1. What is the time efficiency of the DFS approach to topological sort?
2. Consider the dag in exercise 4.2.1b.
   1. Use the DFS-based topological sort algorithm to determine a topological sort for the vertices. Use the alphabetical order of the vertices for DFS.
   2. Do the same, but using the reverse alphabetical order for the vertices (so the DFS will start from \(f\)).
   3. Apply the decrease-by-one-and-conquer algorithm for topological sort.