Let us see how we can compute shortest paths in directed acyclic graphs in linear time. A directed acyclic graph (DAG) is a directed graph with no directed cycles. See Figure 1 (a) for an example of a DAG. A source vertex in a directed graph is a vertex with no incoming edges, and a sink vertex in a directed graph is a vertex with no outgoing edges. For example, in Figure 1 (a), vertex A is a source, and vertex F is a sink. B 6 O 5 A N " 12 E 7 3 F 4 B 6 D -5 5 E 3 F 4 C B 6 D 10 -2 5 E F (a) (b) (c) Figure 1: (a) G, a directed acyclic graph (DAG); (b) G, after deleting vertex A; (c) G, after deleting A and C Puzzle 1 (a). Give an example of a directed graph with no source vertex and no sink vertex. If we delete A and all its adjoining edges from the graph Figure 1 (a), then we are left with the graph Figure 1 (b), in which C is a source vertex. And if we delete C and all its adjoining edges from Figure 1 (b), then we are left with the graph Figure 1 (c), in which B is a source vertex. Puzzle 1 (b). Prove that the above is true for all DAGS. In other words, prove that every DAG on n vertices contains at least one source vertex and at least one sink vertex. If you delete a source vertex and all its adjoining edges from the DAG, then the remaining DAG on (n-1) vertices also contains a source vertex. And if you delete that vertex and all its adjoining edges, then the remaining DAG on (n-2) vertices also contains a source vertex. You can keep deleting vertices in this manner, till you are left with only one vertex. Puzzle 1 (c). Using the above idea, design an linear-time algorithm SHORTESTPATHDAG to find a shortest path in a given DAG. SHORTESTPATHDAG(V, E, s, t, w) SHORTESTPATHDAG(V, E, s, t, w) takes as input a DAG G with vertex set V, edge set E, two vertices s V and te V, and a weight function w on the edges of G. For every edge e E, its weight w(e) is a positive integer. Your algorithm should output a shortest path from s to t in G. Write down the complete code/pseudo-code of your algorithm and provide a proof of its correctness. Also prove that its running time is O(IV+E). You Puzzle 1 (c). Using the above idea, design an linear-time algorithm SHORTESTPATHDAG to find a shortest path in a given DAG. SHORTESTPATHDAG(V, E, s, t, w) SHORTESTPATHDAG(V, E, s, t, w) takes as input a DAG G with vertex set V, edge set E, two vertices s V and t EV, and a weight function w on the edges of G. For every edge e E, its weight w(e) is a positive integer. Your algorithm should output a shortest path from s to t in G. Write down the complete code/pseudo-code of your algorithm and provide a proof of its correctness. Also prove that its running time is O(IV+ |E|). You may use the graph in Figure 1 (a) as a running example in your proof. 1 Puzzle 1 (d). Does your algorithm work for DAGS with negative edge weights also? If yes, then provide a proof. If no, then provide an example of a graph for which it fails.