Question 4 Longest increasing subsequence: Given an input sequence X = (X1, X2, ..., Xn) of numbers, an increasing subsequence of X is a subsequence where the values are increasing in value. We would like to find the longest increasing subsequence. For simplicity, assume that all the numbers in X are distinct. 1. Develop a recursive formula for the problem above and prove the correct- ness of the formula, i.e., show that it yields an optimal answer. 2. Write down a pseudo code for a top-down recursive algorithm using the formula developed in (a). 3. Describe a bottom-up dynamic programming iterative algorithm for the problem. Write down the pseudo code and establish its running time. 4. Use your bottom-up algorithm to solve the problem for the input X = (13, 36, 40, 41, 19, 43, 37, 10). Show the final tabulation and write down the final answer. Question 4 Longest increasing subsequence: Given an input sequence X = (X1, X2, ..., Xn) of numbers, an increasing subsequence of X is a subsequence where the values are increasing in value. We would like to find the longest increasing subsequence. For simplicity, assume that all the numbers in X are distinct. 1. Develop a recursive formula for the problem above and prove the correct- ness of the formula, i.e., show that it yields an optimal answer. 2. Write down a pseudo code for a top-down recursive algorithm using the formula developed in (a). 3. Describe a bottom-up dynamic programming iterative algorithm for the problem. Write down the pseudo code and establish its running time. 4. Use your bottom-up algorithm to solve the problem for the input X = (13, 36, 40, 41, 19, 43, 37, 10). Show the final tabulation and write down the final