Please start every subpart on a separate page.

1 [15 points]. Recall the LIS problem for the string A[1...n] over integers (A may have duplicate symbols). Consider these definitions.
M(i,j) = set of increasing subsequences in A[1 ... i] of length j, could be empty. Always empty if j > i.
m(i,j) = subsequence in M(i,j) with the smallest last symbol (terminating, right-most symbol), null if M(i,j) is empty
l(i,j) = last symbol of m(i,j), infinity when M(i,j) is empty

Ex, if M(i,4) = { (2,3,4,5), (1,4,5,7) } then m(i,4) = (2,3,4,5)
For the above example, l(i,4) = 5

(a) [3 points] Prove that if m(i,j) is not null and ends in A[i] then l(i-1,j-1) < A[i] <= l(i-1,j).
Try to prove the two inequalities separately.

(b) [2 points] Prove that if m(i,j) is not null and does not end in A[i] then either A[i] <= l(i-1,j-1) or A[i] > l(i-1,j).

For (a) and (b), j is at least 2.

(c) [5 points] Using (a) and (b) give a recursive backtracking algorithm for computing any l(i,j) value.

(d) [2 points] Design an algorithm to compute the length of the longest increasing subsequence of A using the algorithm to compute the l(i,j) values.

(e) [3 points] Analyse the time complexity of your algorithm in (d).