Vishals algorithm: Your friend Vishal suggests an alternate algorithm to find a linearization of a DAG G. Vishals algorithm runs DFS and then outputs vertices in order of increasing pre values. He claims that his algorithm is correct. In this question, you are asked to come up with a counterexample to Vishals claim, thereby disproving it. Please break your answer into the following parts: a) (2pts) Draw a graph which disproves Vishals claim. You should label each vertex with a letter, i.e. A, B, etc... b) (2pts) Give the pre numbers output by DFS on this graph. As we do in class, run DFS using the alphabetical ordering of the vertices. c) (2pts) Give the list of vertices output by Vishals algorithm. d) (2pts) List at least one edge that violates the validity of this ordering.

3. (8 pts.) Vishal's algorithm: Your friend Vishal suggests an alternate algorithm to find a linearization of a DAG G. Vishal's algorithm runs DFS and then outputs vertices in order of increasing pre values. He claims that his algorithm is correct. In this question, you are asked to come up with a counterexample to Vishal's claim, thereby disproving it. Please break your answer into the following parts: a) (2pts) Draw a graph which disproves Vishal's claim. You should label each vertex with a letter, i.e. 'A', 'B', etc... b) (2pts) Give the pre numbers output by DFS on this graph. As we do in class, run DFS using the alphabetical ordering of the vertices. c) (2pts) Give the list of vertices output by Vishal's algorithm. d) (2pts) List at least one edge that violates the validity of this ordering