**Paper, Order, or Assignment Requirements**

** **

Please see questions in the uploaded file

- Suppose you have a chain of 11 matrices, with dimensions given by the

12-tuple, . Thus, has dimensions and in general, has dimensions for . Specifically, the 12-tuple is

(5, 10, 9, 20, 6, 33, 5, 17, 12, 8, 16, 5). How should you multiply the matrices in this chain so as to minimize the total number of numeric multiplications? Give your answer both as a parenthesization of the chain of matrices and also as the 10 specific matrix multiplications in order that produce this minimal number. (For example, if you were to multiply times followed by a multiplication on the right by , you could indicate these steps in order as:

(1) Compute

(2) Compute

And so forth (I am not claiming that these steps would necessarily occur.) Important: Show your work!

- The first stanza of King Lear’s famous Act III scene 2 speech, with all of the punctuation and spaces removed and all lower case (from First Folio, 1623 edition, with original spelling) is:

blowwindesandcrackyourcheeksrageblowyoucataractsandhyrricanosspouttillyouhaueddrenchdoursteeplesdrownthecockesyousulphrousandthoughtexecutingfiresvauntcurriorsofoakecleauingthunderboltssingemywhiteheadandthouallshakingthunderstrikeflatthethickerotundityothworldcrackenaturesmouldsallgermainesspillatoncethatmakesingratefullman

Find the longest palindromic subsequence in this text and its length. Again, show your work. Also, take your full name, all lower case and with spaces and punctuation removed. What is the longest palindromic subsequence in it and what is its length?

- Read the textbook discussion about Strassen’s divide and conquer algorithm for matrix multiplication. The square of an n n matrix, A, is its product with itself, AA.

(a) Show that the square of a 2 2 matrix can be computed with five numeric multiplications (that is, multiplications of floating point numbers.)

(b) What is wrong with the following divide-and-conquer algorithm, influenced by the Strassen algorithm (see textbook) for computing the square of an n n matrix: “Use a divide-and-conquer approach in which you partition the matrix and produce five problems, each of size n/2, via part (a) (vs. the 7 subproblems each of size n/2 for the Strassen algorithm for more general matrix multiplication.) Thus, the algorithm for squaring an n n runs in time

(c) Squaring a matrix is actually no easier, in terms of complexity, than matrix multiplication. Show this in the following way: Show that any matrix squaring algorithm can be used to multiply two

n n matrices and thus conclude that if an n n matrix can be squared in time then two

n n can be multiplied in time (same c.)

(4) For each of the following problems, identify a sequence of decisions to solve the problem and show that the Principle of Optimality holds for the problem:

a.) You have a collection of N different types of blocks, and as many blocks of each type as you need. Each block is closed and rectangular with dimensions a_{i} by b_{i} by c_{i} (for block type i.) You goal is to stack the blocks to create as tall a tower as possible (you may use more than one of each block.) The restriction, though, is that for stability, if a block is placed on top of another block, the corresponding lengths and widths must be parallel and the block on top must have those dimensions strictly smaller than the corresponding dimensions of the block below.

b.) You have a chessboard which is N by N. You have a token which you will place in a square at one side of the board and move across the board to the other side. The start side and the finish side are given. A legal move is to move either straight ahead to the next square, move diagonally to the left forward square (unless you are at the leftmost square), or move diagonally to the right forward square (unless you are at the rightmost square.) For each legal move, from square x to square y, there is a point award, f(x, y). Your goal is to get a maximum number of points. You may choose any square on the start side to start and end up at any square on the finish side to end.

(5) Suppose that T[1…N] is a sorted (in increasing order) array of distinct integers, some of which might be negative. Give an algorithm that can find an index *i* such that 1 *i* and T[*i*] = *i*, provided that such an index exists, or so state if no such index exists. Your algorithm should take **O**(logN) in worst case. Explain why your algorithm always works and why the run time complexity is **O**(logN).

(6) You are to organize a tournament involving N competitors. Each competitor must play exactly once against each possible opponent. Moreover, each competitor must play exactly one match every day, with the possible exception of a single day when he or she does not play at all.

(a) If N is a power of 2, design a divide and conquer algorithm to construct a time table allowing the tournament to be finished in N-1 days.

(b) For any N > 1 give an algorithm to construct a time table allowing the tournament to finish in N-1 days if N is even or N days if N is odd.

Notes: Yes, I know that (b) can be used in (a), but I want you to solve (a) first and then generalize to (b). Please explain and justify your answers.

**This is a divide and conquer question!! To receive credit, you must approach this problem with the divide and conquer heuristic.**

(7) We discussed the possibility of a greedy algorithm for the chain matrix products problem, where we are given positive integers d_{0}, d_{1}, d_{2}, …, d_{N}, which are such that a matrix A_{k} has dimensions d_{k-1} d_{k} and we wish to parenthesize A_{1}A_{2}^{…}A_{N} so as to minimize the number of numeric multiplications in computing that matrix product. For each of the following reasonable heuristic values, provide a counterexample (with proof) for why the greedy algorithm doesn’t work:

(a) Multiply in the remaining chain the pair of matrices whose common dimension is largest.

(b) Multiply in the remaining chain the pair of matrices whose common dimension is smallest.

(c) Multiply in the remaining chain the pair of matrices whose triple product (#rows of the left * #columns of the right * common dimension) is smallest.

(d) Multiply in the remaining chain the pair of matrices whose triple product (#rows of the left * #columns of the right * common dimension) is largest.

(8) You have N objects that you wish to put in order using the relations “<” and “=”. As an example, if you have N = 3 objects (say a, b, and c) then there are 13 different orderings possible:

a = b = c a = b < c a < b = c a < b < c a < c < b

a = c < b b < a = c b < a < c b < c < a b = c < a

c < a = b c < a < b c < b < a

(a) Explain why these are all of the possible orderings in the case N = 3.

(b) Use dynamic programming to calculate, as a function of N, the number of possible orderings. Your algorithm should take time **O**(N^{2}) and space **O**(N).