Faster linearization: In class, we described an algorithm for finding a linearization of a DAG G. The algorithm runs DFS on G, and then outputs the vertices in order of decreasing post values. The run time of this algorithm is O(nlog n+m), because it sorts the vertices as a final step. However, this is actually inefficient and there exists an alternate implementation that runs in O(n + m) time. This implementation is a modification of the DFS algorithm to output the ordering during the execution of the DFS algorithm, thereby avoiding the sorting step in the end. (a) (2pt) What linearization is found by the algorithm in class on the following graph? Make sure you run DFS on the vertices in alphabetical order. (b) (8pt) Please write down pseudocode for a modified version of DFS that takes a graph G and outputs vertices in order of decreased post values. Your algorithm should run in O(n+m) time. You must use pseudocode for this problem.

(10 pts.) Faster linearization: In class, we described an algorithm for finding a linearization of a DAG G. The algorithm runs DFS on G, and then outputs the vertices in order of decreasing post values. The run time of this algorithm is O(nlogn+m), because it sorts the vertices as a final step. However, this is actually inefficient and there exists an alternate implementation that runs in O(n+m) time. This implementation is a modification of the DFS algorithm to output the ordering during the execution of the DFS algorithm, thereby avoiding the sorting step in the end. (a) (2pt) What linearization is found by the algorithm in class on the following graph? Make sure you run DFS on the vertices in alphabetical order. (b) (8pt) Please write down pseudocode for a modified version of DFS that takes a graph G and outputs vertices in order of decreased post values. Your algorithm should run in O(n+m) time. You must use pseudocode for this