### CS2223 Algorithms Homework 6 - D Term 2008

#### PROF. CAROLINA RUIZ

Due Date: Wednesday April 23, 2008 at 1:00 PM
See course policy regarding late homework submissions

• Homework Instructions:
• Read Chapter 6 of the textbook in detail.
• See Useful logarithm and exponential facts.
• This is an individual homework. No collaboration is allowed.
• Submit a hardcopy of your written homework solutions to the box marked CS2223 in the CS office (FL233) before the deadline.
• See the course webpage for the late homework submission policy.

• Homework Problems:

1. (50 Points) Problem 1. Consider the problem of finding the length of the longest (strictly) decreasing subsequence in a given sequence For instance, if the input sequence is:
```  7  3  4  9  2  8  4  5  2  1  6  3  10
```
then the length of the longest decreasing subsequence in this sequence is: 5, and in this case there are two such maximal subsequences:
```  9  8  5  2  1

9  8  4  2  1
```
The input-output description of this problem is:

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)).

2. (50 Points) Problem 2. Consider the problem of finding paths in a grid. For that, imagine that you're in a city where avenues (vertical lines) and streets (horizontal lines) form a perfect grid. Imagine that you're located at the origin of the grid, that is at the intersection of avenue 0 and street 0: (0,0), which is the south-west corner of the city. Given a pair (n,m) denoting the intersection of avenue n with street m, you need to determine how many different paths exist between your current position (0,0) and (n,m).

A path from (0,0) to (n,m) is a sequence (0,0)=(a0,b0),(a1,b1),(a2,b2),...,(ak,bk)=(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) = ai + 1 and b(i+1) = bi, (walking one block east) or
• a(i+1) = ai and b(i+1) = bi + 1 (walking one block north).

2. You cannot walk east of avenue n or north of street m. In other words, ai ≤ n and bi ≤ m, for all ai, bi 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)).