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 valid traversal order is:

[a] Solve A(i, j) for (i from 0 to n: for (j from 0 to n))

[b] Solve A(i, j) for (i from 0 to n-2: for (j from i+2 to n))

[c] Solve A(i, j) for (i from 0 to n-2: for (j from i to n))

[d] none of the above

5. Consider two vertices, s and t, in some directed acyclic graph G = (V, E). Lets 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