Exercises 15.4-6

By the hint and using the binary search method. Every element x in the sequence can find the LIS ended with x in time O(lg n).

Exercises 15.4-5

We can sort sequence X, let the result be Y. Then find the LCS of X and Y, which is LIS.

Exercises 15.4-4

When compute c[i] row , we only need c[i-1] row. Similarly, we can compute j column only use j-1 column. Hence we can use min(m,n) space.

Exercises 15.4-3

Exercises 15.4-2

We can compute the b table’s value in the procedure PRINT-LCS.

Exercises 15.4-1