# Homework 7

Due Monday, February 10 at 5:00 PM. Please refer to the homework policy here. We are hoping to put out solutions for this homework right after the submission deadline, and there will be no homework assigned on Thursday.

1. Let $A[1..m]$ and $B[1..n]$ be two arbitrary arrays. A common super sequence of $A$ and $B$ is another sequence that contains both $A$ and $B$ as subsequences. Describe an efficient algorithm to compute the length of the shortest common supersequence of $A$ and $B$.
2. Problem 42 (a), (b), (c), (d) in Chapter 3 of Jeff's notes.
3. Problem 46 in Chapter 3 of Jeff's notes.

## Template for dynamic programming

For dynamic programming problems, we request you follow the following templates (which I also use in real life).

We will use the longest increasing subsequence problem (see for example Section 3.6 of Jeff's notes). We take as input a sequence $A[1..n]$ of numbers. A subsequence $A[i_1,i_2,\dots,i_k]$ (where $i_1< i_2 < \cdots < i_k$) is "increasing" if we have $A[i_j] < A[i_{j+1}]$ for each $j = 1,\dots,k-1$. For example, in the following sequence, the subsequence of odd numbers form an increasing subsequence.

For this class it suffices to solve things up to 5 parts.

### 1. Semantic definition of the subproblems

LIS(i,j) = Longest increasing subsequence of $A[j..n]$ where each number in the subsequence is $> A[i]$.

### 2. How to extract the overall output from the subproblems

In the examples in class, this was just one particular subproblem. Here we actually take the maximum over some of the subproblems. We give some brief justification here since this is not as simple as just returning an obvious subproblem.

We return the maximum of $(1 + LIS(i,i+1))$ over $i \in [n]$. Here each choice of $i$ corresponds to the maximum length increasing subsequence starting from $A[i]$.

### 3. Recursive spec

Here we give a recursive specification that implements $LIS(i,j)$ per the semantic formulation above. Check your base cases!

Usually the reasoning is transparent from the recursive spec and the correctness follows easily enough that we won't demand a full proof. (Usually the correctness is clear at the level of the semantic problem formulation above.) If there was something much more complicated going on, then some explanation or even a proof would be expected.

### 4. Number of subproblems

We compute $LIS(i,j)$ for $i = 1,\dots,n+1$ and $j = 1,\dots,n+1$, so there are $O(n^2)$ total subproblems.

### 5. Running time analysis

Give the full running time. Here, please mention explicitly that you are "using dynamic programming" or "caching solutions to subproblems" to obtain the faster running time.

Each subproblem $LIS(i,j)$ takes constant time plus work delegated to recursive calls. There are $O(n^2)$ total subproblems. By caching solutions to all subproblems, the total algorithm takes $O(n^2)$ time.

Another example of a worked out solution is given in Homework 5 of Jeff's Spring 2018 course. Note that our rubric is a little simpler in that we don't ask for a space bound (which is usually the number of subproblems, with some exceptions) or any explicit mention if the iteration order (which is usually straightforward or implicit in the correctness). Here our emphasis is on getting the subproblem definition correctly and implementing the recursive spec correctly.