(Solved): 4 Counting Simple Paths in a DAG (45 pts) In this problem you will design an algorithm that takes ...

4 Counting Simple Paths in a DAG (45 pts) In this problem you will design an algorithm that takes as input a directed acyclic graph $$G=(V,E)$$ and two vertices $$s$$ and $$t$$, and returns the number of simple paths from $$s$$ to $$t$$ in $$G$$. For example, the directed acyclic graph below contains exactly four simple paths from vertex $$p$$ to vertex $$v$$ : pov, poryv, posryv, and psryv. Notice: your algorithm needs only to count the simple paths, not list them. (a) (15 pts) Design a recursive backtracking (brute-force) algorithm that determines the number of paths from $$s$$ to $$t$$. Write down the pseudocode of your algorithm and prove its correctness, i.e., convince us that it works beyond any doubt. (Hint: using induction.) A solution with no proof will receive 0 points! Make your pseudocode as simple as possible. You will be graded on the elegance of your solution, not just the correctness. (b) (15 pts) Modify your pseudocode in part (a) to use memoization. Write down the modified pseudocode and explain your choice of the memoization table and the indices used for memoization. (Hint: What is a natural way to memoize solutions to subproblems that had already been computed?) (c) (15 pts) Design a bottom-up dynamic programming algorithm that counts the number of simple paths from $$s$$ to $$t$$. Write the pseudocode and analyze its running time. Argue why your choice of the order in which you fill in the values is the correct one. (Hint: Think about the order on which the computation of the paths from each vertex depends.)