# 15.4 Longest common subsequence

## 15.4-1

Determine an $\text{LCS}$ of $\langle 1, 0, 0, 1, 0, 1, 0, 1 \rangle$ and $\langle 0, 1, 0, 1, 1, 0, 1, 1, 0 \rangle$.

$\langle 1, 0, 0, 1, 1, 0 \rangle$.

## 15.4-2

Give pseudocode to reconstruct an $\text{LCS}$ from the completed $c$ table and the original sequences $X = \langle x_1, x_2, \ldots, x_m \rangle$ and $Y = \langle y_1, y_2, \ldots, y_n \rangle$ in $O(m + n)$ time, without using the $b$ table.

1 2 3 4 5 6 7 8 9 10 | PRINT-LCS(c, X, Y, i, j) if c[i, j] == 0 return if X[i] == Y[j] PRINT-LCS(c, X, Y, i - 1, j - 1) print X[i] else if c[i - 1, j] > c[i, j - 1] PRINT-LCS(c, X, Y, i - 1, j) else PRINT-LCS(c, X, Y, i, j - 1) |

## 15.4-3

Give a memoized version of $\text{LCS-LENGTH}$ that runs in $O(mn)$ time.

1 2 3 4 5 6 7 8 | MEMOIZED-LCS-LENGTH(X, Y, i, j) if c[i, j] > -1 return c[i, j] if i == 0 or j == 0 return c[i, j] = 0 if x[i] == y[j] return c[i, j] = LCS-LENGTH(X, Y, i - 1, j - 1) + 1 return c[i, j] = max(LCS-LENGTH(X, Y, i - 1, j), LCS-LENGTH(X, Y, i, j - 1)) |

## 15.4-4

Show how to compute the length of an $\text{LCS}$ using only $2 \cdot \min(m, n)$ entries in the $c$ table plus $O(1)$ additional space. Then show how to do the same thing, but using $\min(m, n)$ entries plus $O(1)$ additional space.

Since we only use the previous row of the $c$ table to compute the current row, we compute as normal, but when we go to compute row $k$, we free row $k - 2$ since we will never need it again to compute the length. To use even less space, observe that to compute $c[i, j]$, all we need are the entries $c[i − 1, j]$, $c[i − 1, j − 1]$, and $c[i, j − 1]$. Thus, we can free up entry-by-entry those from the previous row which we will never need again, reducing the space requirement to $\min(m, n)$. Computing the next entry from the three that it depends on takes $O(1)$ time and space.

## 15.4-5

Give an $O(n^2)$-time algorithm to find the longest monotonically increasing subsequence of a sequence of $n$ numbers.

Given a list of numbers $L$, make a copy of $L$ called $L'$ and then sort $L'$.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | PRINT-LCS(c, X, Y) n = c[X.length, Y.length] let s[1..n] be a new array i = X.length j = Y.length while i > 0 and j > 0 if x[i] == y[j] s[n] = x[i] n = n - 1 i = i - 1 j = j - 1 else if c[i - 1, j] ≥ c[i, j - 1] i = i - 1 else j = j - 1 for i = 1 to s.length print s[i] |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 | MEMO-LCS-LENGTH-AUX(X, Y, c, b) m = |X| n = |Y| if c[m, n] != 0 or m == 0 or n == 0 return if x[m] == y[n] b[m, n] = ↖ c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y[1..n - 1], c, b) + 1 else if MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b) ≥ MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b) b[m, n] = ↑ c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b) else b[m, n] = ← c[m, n] = MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b) |

1 2 3 4 | MEMO-LCS-LENGTH(X, Y) let c[1..|X|, 1..|Y|] and b[1..|X|, 1..|Y|] be new tables MEMO-LCS-LENGTH-AUX(X, Y, c, b) return c and b |

Then, just run the $\text{LCS}$ algorithm on these two lists. The longest common subsequence must be monotone increasing because it is a subsequence of $L'$ which is sorted. It is also the longest monotone increasing subsequence because being a subsequence of $L'$ only adds the restriction that the subsequence must be monotone increasing. Since $|L| = |L'| = n$, and sorting $L$ can be done in $o(n^2)$ time, the final running time will be $O(|L||L'|) = O(n^2)$.

## 15.4-6 $\star$

Give an $O(n\lg n)$-time algorithm to find the longest monotonically increasing subsequence of a sequence of $n$ numbers. ($\textit{Hint:}$ Observe that the last element of a candidate subsequence of length $i$ is at least as large as the last element of a candidate subsequence of length $i - 1$. Maintain candidate subsequences by linking them through the input sequence.)

The algorithm $\text{LONG-MONOTONIC}(S)$ returns the longest monotonically increasing subsequence of $S$, where $S$ has length $n$.

The algorithm works as follows: a new array B will be created such that $B[i]$ contains the last value of a longest monotonically increasing subsequence of length $i$. A new array $C$ will be such that $C[i]$ contains the monotonically increasing subsequence of length $i$ with smallest last element seen so far.

To analyze the runtime, observe that the entries of $B$ are in sorted order, so we can execute line 9 in $O(\lg n)$ time. Since every other line in the for-loop takes constant time, the total run-time is $O(n\lg n)$.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | LONG-MONOTONIC(S) let B[1..n] be a new array where every value = ∞ let C[1..n] be a new array L = 1 for i = 1 to n if A[i] < B[1] B[1] = A[i] C[1].head.key = A[i] else let j be the largest index of B such that B[j] < A[i] B[j + 1] = A[i] C[j + 1] = C[j] INSERT(C[j + 1], A[i]) if j + 1 > L L = L + 1 print C[L] |