#4 (9 pts) Counting Simple Paths in a DAG Design an algorithm that takes as input a directed acyclic graph G vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph on the right contains exactly four simple paths from vertex p to vertex v: pov, poryv, posryv, and psryv. Your algorithm should run in time O(V+E). (Your algorithnm needs only to count the simple paths, not list them.) (V, E) and two Hints: Solve the more general case of number of paths to all vertices. Use topological sort to solve smaller problems before larger ones. Be sure to consider the boundary cases where s t and where there are no simple paths between s and t (a) (b) (c) (5 pts) Write the pseudocode (2 pts) Explain why it works (2 pts) Analyze its asymptotic run time #4 (9 pts) Counting Simple Paths in a DAG Design an algorithm that takes as input a directed acyclic graph G vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph on the right contains exactly four simple paths from vertex p to vertex v: pov, poryv, posryv, and psryv. Your algorithm should run in time O(V+E). (Your algorithnm needs only to count the simple paths, not list them.) (V, E) and two Hints: Solve the more general case of number of paths to all vertices. Use topological sort to solve smaller problems before larger ones. Be sure to consider the boundary cases where s t and where there are no simple paths between s and t (a) (b) (c) (5 pts) Write the pseudocode (2 pts) Explain why it works (2 pts) Analyze its asymptotic run time