3. In dynamic programming algorithm, we drive a recurrence relation for the solution to one subproblem in terms of solution to others and reuse the solutions to smaller subproblems in order to solve a larger problem. Suppose the recurrence relation for a dynamic programming algorithm is of the form: The number of subproblems is: 4 a] 3n b] 2n [c] n2 [d] none of the above 4. In bottom-up dynamic programming algorithm, we need a traversal order such that all needed subproblems are solved before solving the original problem. Suppose the recurrence relation for a dynamic programming algorithm is of the form: A(i,j)-f(A(i-2.j-2), A(i +2.j+2- 0.1 2 A valid traversal order is [a] Solve Ai, j) for (i from 0 to n: for (G from 0 to n)"I b] Solve A(i, j) for (i from 0 to n-2: for G from i+2 to n)) [c] Solve A(i, j) for (i from 0 to n-2: for G from i to m)) [d] none of the abovee 5. Consider two vertices, s and t, in some directed acyclic graph G- (V, E). Let's assume that a dynamic programming algorithm is developed to determine the number of paths in G from s to t. The running time of the algorithm is: [a] O (VE) b] O (V+E) [c] O (VlgV+E). [d] none of the above*