Skip to content

Latest commit

 

History

History
109 lines (84 loc) · 3.91 KB

15.4.md

File metadata and controls

109 lines (84 loc) · 3.91 KB
Raw

Exercises 15.4-1

Determine an LCS of <1, 0, 0, 1, 0, 1, 0, 1> and <0, 1, 0, 1, 1, 0, 1, 1, 0>.

Answer

The LCS is <1, 0, 0, 1, 1, 0> , Or It can be <1,0,1,0,1,0>

Exercises 15.4-2

Show how to reconstruct an LCS from the completed c table and the original sequences X = <x1, x2, ..., xm> and Y = <y1, y2, ..., yn> in O(m +n) time, without using the b table.

Answer

PRINT_LCS(c, x, y, i, j)
	if i = 0 || j = 0
		return
	if x[i] = y[j]
		PRINT_LCS(c, x, y, i-1, j-1)
		print x[i]
	elif 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)

Exercises 15.4-3

Give a memoized version of LCS-LENGTH that runs in O(mn) time.

Answer

LCS-LENGTH(X, Y)
	m ← length[X]
	n ← length[Y]
	for i ← 1 to m do
		for j ← 1 to n do
			c[i,j] ← -1
		end for
	end for
	return LOOKUP-LENGTH(X,Y,m,n)
	
LOOKUP-LENGTH(X,Y,i,j)
	if c[i,j] > -1 then
		return c[i,j]
	end if
	if i = 0 or j = 0 then
		c[i,j] ← 0
	else
		if X[i] = Y[j] then
			c[i,j] ← LOOKUP-LENGTH(X,Y,i-1,j-1)+1
		else
			c[i,j] ← max(LOOKUP-LENGTH(X,Y,i,j-1),LOOKUP-LENGTH(X,Y,i-1,j))
		end if
	end if
	return c[i,j]

Exercises 15.4-4

Show how to compute the length of an LCS using only 2 · min(m, n) entries in the c table plus O(1) additional space. Then show how to do this using min(m, n) entries plus O(1) additional space.

Answer

因为求解一个项c[i,j],只会用到c[i-1,j-1],c[i,j-1],c[i-1,j]. 所以运行时刻,我们只需要保存上面一行的状态和当前行的状态即可,再令X,Y这两个字符串中短的那一个放到index j.所以可以用2 · min(m, n)的空间运行算法.

那如何做到只利用min(m, n) entries plus O(1) additional space呢? 其实我们只需要用一行保存状态即可. c[i,j-1]已经保存在该行中. 然后用一个常量维护c[i-1,j-1]即可.每次更新c[i,j]的时候将old valuy保存下来,因为下次要用到.

Since we need only c[i-1,j-1], c[i,j-1], c[i-1,j] to compute c[i,j], we just need to save the previous row and the current row of the dp table. We will maintain the row parallel to the shorter one of the X and Y strings. So we can run the algorithm with 2 · min(m, n) space.

In fact, we only need to save only one row. c[i,j-1] is already stored in this row. Then, we use an extra variable to maintain c[i-1,j-1]. Every time c[i,j] is updated, the value of c[i-1,j] is saved into the extra variable because it will be used next time.

Exercises 15.4-5

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

Answer

Method 1: Given a sequence X = <x1,x2,...,xn> we wish to find the longest monotonically increasing subsequence.

  1. First we sort the string X which produces sequence X'.

  2. Finding the longest common subsequence of X and X' yields the longest monotonically increasing subsequence of X.

The running time is O(n^2) since sorting can be done in O(nlgn) and the call to LCS-LENGTH is O(n^2).

Method 2: LONGEST-INC-SEQUENCE(Arr, n) len [1...n] be a new array for i←1 to n len[i] ← 1 // length of longest increasing sequence ending at i. for i←2 to n do for j←1 to i-1 do if Arr[j] < Arr[i] len [i] ← max(len[i], len[j] +1) end if end for end for return len [n]

Exercises 15.4-6 *

Give an O(n lg n)-time algorithm to find the longest monotonically increasing sub-sequence of a sequence of n numbers. (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.)

Answer

implementation

Follow @louis1992 on github to help finish this task.