1. Longest Increasing Subsequence (8 points) Consider the following problem Input: An array A[1...n] of integers Output: The largest integer m such that the array A[1...n] has subsequence of length m which is strictly increasing The following pseudocode finds the length of the longest of the given array A[1...n] by considering all possible subsequences Algorithm 1 longestSubSeq( int A[1...n] ) 2: while (true) do 3: //(I) A does not contain an increasing subsequence of length > n -k Let B = A with k elements removed if ( isIncreasing(B)) then 6: 7: return n - k; end if 9:while ( there are other possible choices of k elements to remove) 10: k ++ 11: end while The following code checks if an array is increasing (i.e., each number is smaller than the next in the array) Algorithm 2 isIncreasing( int C|1 n ) 2: whilei C[i+ 1] ) then return false; 5: end if 6: 7: end while 8: return true; Example: longestSubSeq( [2, 4, 3,8,5,5,6,7,9]) returns 6 Justification: [2,4, X, X, 5,X, 6, 7,9-[2, 4,5,6,7,9] which is a longest increas- ing subsequence of the original array. 1. Longest Increasing Subsequence (8 points) Consider the following problem Input: An array A[1...n] of integers Output: The largest integer m such that the array A[1...n] has subsequence of length m which is strictly increasing The following pseudocode finds the length of the longest of the given array A[1...n] by considering all possible subsequences Algorithm 1 longestSubSeq( int A[1...n] ) 2: while (true) do 3: //(I) A does not contain an increasing subsequence of length > n -k Let B = A with k elements removed if ( isIncreasing(B)) then 6: 7: return n - k; end if 9:while ( there are other possible choices of k elements to remove) 10: k ++ 11: end while The following code checks if an array is increasing (i.e., each number is smaller than the next in the array) Algorithm 2 isIncreasing( int C|1 n ) 2: whilei C[i+ 1] ) then return false; 5: end if 6: 7: end while 8: return true; Example: longestSubSeq( [2, 4, 3,8,5,5,6,7,9]) returns 6 Justification: [2,4, X, X, 5,X, 6, 7,9-[2, 4,5,6,7,9] which is a longest increas- ing subsequence of the original array