For dynmamic programming algorithms, you should:

• Define the table - What does each element of the table hold?

• Give a formula for filling in table locations - this should include both a base case and a recursive case.

• Describe the order in which the table will be filled in (a picture is a good idea here)

• Give pseudocode for your algorithm

1. We want to multiply a chain of matrices together:

M1M2M3M4 . . . Mn

where Mk has dimensions pk-1 × pk for p0 . . . pn.

We want to multiply these matrices in a way that minimizes the total number of scalar multiplications. Show that none of the following greedy algorithms produce optimal solutions in all cases:

(a) First multiply the matrices Mi and Mi+1 whose common dimension is smallest. Recursively find a solution for multiplying M1 ∗. . .∗Mi-1 ∗(Mi ∗Mi+1)∗ . . . ∗ Mn

(b) First multiply the matrices Mi and Mi+1 whose common dimension is largest. Recursively find a solution for multiplying M1 ∗ . . . ∗ Mi-1 ∗ (Mi ∗ Mi+1) ∗ . . . ∗ Mn

(c) Split the problem of multiplying Mi ∗ . . . ∗ Mj into the subproblems of multiplying Mi ∗ . . . ∗ Mk and multiplying Mk+1 ∗ . . . ∗ Mj so that pi-1pkpj is minimized. Recursively solve the subproblems of multiplying Mi . . . Mk and Mk+1 . . . Mj, then multiply the results of the subproblems.

2. Consider the alphabet Σ = {a, b, c} the elements of Σ have the following multiplication table, which is neither communative nor associative:

so, ab = b, ba = c, bc = a, cb = c, and so on.

(a) Find a dynamic programming algorithm that examines a string x = x1x2x3 . . . xn and decides whether or not it is possible to parenthesize x such that the value of the resulting expression is a. For example, if x = bbbba, your algorithm should retun "yes", since (b(bb))(ba) = a For the string x = bac, your algorithm should return "no" (since (ba)c = c and b(ac) = c

(b) Modify your algoritm from part a so that instead of returning yes or no, it returns the number of was the expression can be parenthesized to ge the answer a.

3. (8 points) A palindrome is a non-empty string over some alphabet that reads the same forward and backward. Example palendromes are all strings of length 1, civic, racecar, and aibohphobia (fear of palindromes) Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input character, your algorithm should return carac. What is the running time of your algorithm?

4. (8 points) Edit Distance In order to transform one string of text x[1 . . . m] to a target string y[1 . . . n], we can perform various transformational operations. Our goal is, given x and y, to produce a series of transformations that changes x to y. We use an array z - assumed to be large enough to hold all of the characters it will need - to hold the intermediate results.

Initially, z is empty, and at termination, we should have z[j] = y[j] for j = 1, 2 . . . , n. We maintain current indices i into x and j into z, and the operations are allowed to alter z and these indices. Initially, i = j = 1. We are required to examine every character in x during the transformation, which means that at the end of the sequence of transformation operations, we must have i = m + 1 There are six transformation operations:

• Copy a character from x to z by setting z[j] ← x[i] and then incrementing both i and j. This operation examines x[i]

• Replace a character from x by another character c, by setting z[j] ← c, and then incrementing i and j. This operation examines x[i]

• Delete a character from x by incrementing i and leaving j alone. This operation examine x[i]

• Insert the character c into z by setting z[j] ← c and then incrementing j, but leaving i alone. This operation examines no characters of x

• Twiddle (i.e., exchange) the next two characters by copying them from x to z but in the opposite order; we do so by setting z[j] ← x[i + 1] and z[j + 1] ← x[i] and then setting i ← i + 2 and j ← j + 2. This operation examines x[i] and x[i + 1]

• Kill the remainder of x by setting i ← m + 1. This operation examines all characters in x that have not yet been examined. If this operation is performed, it must be the final operation

Each of the transformation operations has an associated cost. The cost of an operation depends on the specific application, but we assume that the individual costs are known to us. We also assume that the individual costs of copy and replace operations are less than the combined costs of the delete and insert operations; otherwise, the copy and replace operations would never be used. The cost of a given sequence of transformation operations is the sum of the costs of the individual operations in the sequence.

Given two sequences x[1 . . . m] and y[1 . . . n] and a set of transformation operator costs, the edit distance from x to y is the cost of the least expensive operation sequence that transforms x to y. Describe a dynamic programming algorithm that finds the edit distance from x[1 . . . m] to y[1 . . . n] and prints an optimal operation sequence. Analyze the running time and space requirements of your algorithm