辅导LCS留学生、辅导R编程语言、讲解subsequence、辅导R设计

Problem 18. (Difficulty 2) Recall that in the dynamic programming algorithm for finding

the length of a longest common subsequence between two strings S and T, we define

the subproblem LCS(i, j) to be the length of a longest common subsequence between the

substrings S[1..i] and T[1..j], and we have the recurrence

LCS(i, j) = (

max{LCS(i 1, j), LCS(i, j 1)} if S[i] 6= T[j]

LCS(i 1, j 1) + 1 if S[i] = T[j].

Suppose S = ALBAI and T = BILAAC. Fill out the matrix that contains the value for each

subproblem LCS(i, j).

For example, if S = ADH and T = JALH, then we have the following matrix:ij

0 1 2 3 4

0 0 0 0 0 0

1 0 0 1 1 1

2 0 0 1 1 1

3 0 0 1 1 2

Problem 19. (Difficulty 3) There are n trading posts numbered 1 to n as you travel downstream.

At any trading post i you can rent a canoe to be returned at any of the downstream

trading post j > i. You are given a cost array R, where R(i, j) is the cost of renting a canoe

from post i to j for 1 ≤ i < j ≤ n. You cannot go upstream. Design a dynamic programming

algorithm to compute the cheapest cost to get from post 1 to n. Make your algorithm as

fast as you can.

For example, suppose n = 4 and the cost matrix R(i, j) is ij

1 2 3 4

1 - 2 3 7

2 - - 2 4

3 - - - 2

4 - - - -

The cheapest way to reach post 4 from 1 is by renting a canoe from 1 to 3, and then from 3

to 4 for a total cost of 3 + 2 = 5.

Problem 20. (Difficulty 3) Describe an O(n2)-time algorithm to compute a longest increasing

subsequence of a sequence of n numbers. Note you have to output the entire sequence,

not just its length. Also recall that the elements of a subsequence need not be consecutive.

Problem 21. Given an n × n matrix A(i, j) of integers, determine in O(n2) time the maximum

value A(c, d) A(a, b) over all choices of indexes such that both c > a and d> b.