7  3  4  9  2  8  4  5  2  1  6  3  10

  9  8  5  2  1 

  9  8  4  2  1 

Input: A sequence S = a1,a2,...,an (you can assume that the sequence is stored in an array) of length n, where each ai is a real number.

Output: Your pseudo-code should print the following output:

1. The length L of the longest strictly decreasing subsequence in S, and
2. The longest (length = L) strictly decreasing subsequence in S (or one of them, if more than one exists).

Solve this problem following the steps below.

1. (12 Points) Dynamic Programming Solution. Design a dynamic programming solution to this problem. Explain in detail how you plan to divide this problem into subproblems, in what order you plan to solve the subproblems so that the solutions to smaller subproblems are available to larger subproblems, and how you plan to use the solutions of these subproblems to produce a solution to the original problem.

2. (12 Points) Algorithm. Write a dynamic programming algorithm (in detailed pseudo-code) implementing the solution you designed above.

3. (13 Points) Correctness. Prove in detail that your algorithm is correct with respect to the input-output specification above.

4. (13 Points) Time Complexity. Analyze in detail the runtime T(n) of your algorithm. Remember to explicitly state what the size of the input is. Find the tightest asymptotic upper bound g(n) for T(n) you can, so that T(n) = O(g(n)).

A path from (0,0) to (n,m) is a sequence (0,0)=(a₀,b₀),(a₁,b₁),(a₂,b₂),...,(a_k,b_k)=(n,m) satisfying the following constraints:

1. You can only walk one block to the east (right) or one block to the north (up) at a time, and only on the avenues and on the streets (no diagonal moves allowed). For instance, a possible path to go from (0,0) to (2,3) is: (0,0), (0,1), (1,1), (1,2), (1,3), (2,3). The sequence (0,0), (1,1), (2,2), (2,3) is NOT a valid path, because it "cuts corners", and the sequence (0,0),(2,0),(2,3) is NOT a valid path because it skips intersections. Hence, for every i < k in the path:

   • a_(i+1) = a_i + 1 and b_(i+1) = b_i, (walking one block east) or
   • a_(i+1) = a_i and b_(i+1) = b_i + 1 (walking one block north).

2. You cannot walk east of avenue n or north of street m. In other words, a_i ≤ n and b_i ≤ m, for all a_i, b_i with i ≤ k.

Assume that there is exactly one path to go from a grid position to itself. The input-output description of this problem is:

Input: Two integers n and m, with n ≥ 0, m ≥ 0.

Output: The total number of different paths on the grid from (0,0) to (n,m) satisfying the two constraints above.

Solve this problem following the steps below.

1. (12 Points) Dynamic Programming Solution. Design a dynamic programming solution to this problem. Explain in detail how you plan to divide this problem into subproblems, in what order you plan to solve the subproblems so that the solutions to smaller subproblems are available to larger subproblems, and how you plan to use the solutions of these subproblems to produce a solution to the original problem.

2. (12 Points) Algorithm. Write a dynamic programming algorithm (in detailed pseudo-code) implementing the solution you designed above.

3. (13 Points) Correctness. Prove in detail that your algorithm is correct with respect to the input-output specification above.

4. (13 Points) Time Complexity. Analyze in detail the runtime T(n,m) of your algorithm. Remember to explicitly state what the size of the input is. Find the tightest asymptotic upper bound g(n,m) for T(n,m) you can, so that T(n,m) = O(g(n,m)).