Let A be an array of letters of the English alphabet. Recall that a subarray of A is of the form A, A,…, A. An array is palindromic if it is the same whether read left to right or right to left. Design a Dynamic Programming algorithm that takes as input an array A and returns the Longest Palindromic Subarray.  Example: A=, your algorithm should return the subarray from index 3 to 9, namely .   Please answer the following parts: Define the entries of your table in words. E.g. T(i) or T(i, j) is … State a recurrence for the entries of your table in terms of smaller subproblems.  Don’t forget your base case(s). Analyze an implementation of this recurrence:         A. State the number of subproblems in big-O notation.         B. State the runtime to fill your table using your recurrence from part 2.         C. State how the return is extracted from your table.          D. State the runtime of that return extraction.

The DP table for the LIS is always nondecreasing.

The DP table for the LIS is always nondecreasing.

While implementing Fast Select, you notice that your pivot p satisfies

True or False: T > T and T > T.

While implementing Fast Select, you notice that your pivot p satisfies

Raquel is going on a really long trip, and will need many toys to be entertained. Prof. Brito allows her to use two bags, with capacities respectively. Design a Dynamic Programming algorithm for Raquel such that: given an array W and L for toys numbered , where W is the weight of toy i, and L is the liking coefficient for each toy (the higher L, the more she likes toy i), your algorithm outputs the maximum sum of the L values of both bags. For now, Raquel only has 1 of each toy. Example: W=, L=, , your algorithm should return 8=5+3 as a result of placing toy 2 in the second bag, and toy 4 in the first bag. Note that you can fill the second bag with toys 1 and 4, and place toy 3 in the first bag, but the sum of the L values in this case is 2+3+1=6

The DP table below is the output from the Longest Increasing Subsequence (LIS) algorithm from class, which was run on a sequence A.    1 1 1 2 2 3 4 4   Based on this table, answer questions 12-15.

You are furthermore given the values of the entries of the input A (as a set, not a sequence). True or False: it is possible to reconstruct the sequence A.

In class we described a method, known as chain matrix multiplication (CMM), which determines the fastest way to multiply