Skip to content

Latest commit

 

History

History
90 lines (68 loc) · 3.04 KB

15.4.md

File metadata and controls

90 lines (68 loc) · 3.04 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保存下来,因为下次要用到.

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

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

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.