P1 (25 points) Write a dynamic programming algorithm to solve the longest increasing subsequence (LIS) problem. You are given an array a of n integers. An increasing subsequence is a sequence k indices 0 i1 < i2 < < ik (n1) such that a[i1] < a[i2] < < a[ik] Given a nd the longest increasing subsequence. I.e, an increasing subsequence i1,...,ik whose length k is the longest possible. Example: Input is a : [1,5,2,3,8]. The longest increasing subsequence has length 4. i1 = 0, i2 = 2, i3 = 3, i4 = 4 yielding the elements 1,2,3,8. Let us dene the function lis(a,j,M) as the length of the LIS for the rst j elements of the array (a[0]a[j 1]), where j ranges from 0 to n and all elements of this subsequence are less than M. (A) For the array a : [1,5,2,3,8] write down the values of lis(a,3,2) and lis(a,5,). (B) Write down the base cases for lis(a,0,M). (C) Write down a recurrence for lis(a,j,M) for any j with 1 j n. (D) Describe a bottom-up scheme to memoize the recurrence lis above. Describe the memo table itself: how many rows? how many columns? what do the rows and columns stand for? How are the base cases lled out in the table? How is each entry of the memo table lled out? Also, show how the lled out memo table for the example array a : [1,5,2,3,8]. (E, Extra Credit) Program your dynamic programming scheme in Python. Input to your function is the list a and output should be the LIS itselfP1 (25 points) Write a dynamic programming algorithm to solve the longest increasing subsequence (LIS) problem. You are given an array a of n integers. An increasing subsequence is a sequence k indices 0 i1 < i2 < < ik (n1) such that a[i1] < a[i2] < < a[ik] Given a nd the longest increasing subsequence. I.e, an increasing subsequence i1,...,ik whose length k is the longest possible. Example: Input is a : [1,5,2,3,8]. The longest increasing subsequence has length 4. i1 = 0, i2 = 2, i3 = 3, i4 = 4 yielding the elements 1,2,3,8. Let us dene the function lis(a,j,M) as the length of the LIS for the rst j elements of the array (a[0]a[j 1]), where j ranges from 0 to n and all elements of this subsequence are less than M. (A) For the array a : [1,5,2,3,8] write down the values of lis(a,3,2) and lis(a,5,). (B) Write down the base cases for lis(a,0,M). (C) Write down a recurrence for lis(a,j,M) for any j with 1 j n. (D) Describe a bottom-up scheme to memoize the recurrence lis above. Describe the memo table itself: how many rows? how many columns? what do the rows and columns stand for? How are the base cases lled out in the table? How is each entry of the memo table lled out? Also, show how the lled out memo table for the example array a : [1,5,2,3,8].