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$ or $\langle 1, 0, 1, 0, 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.
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.
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'$.
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]
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)
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}(A)$ returns the longest monotonically increasing subsequence of $A$, where $A$ 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)$.
LONG-MONOTONIC(A)
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]