1. Say we want to find an order for multiplying a sequence of matrices which MAXIMIZES the number of scalar multipies required. Can we use a similar dynamic programming algorithm? If so, describe how to change the algorithm and argue in a few sentences that it is still correct. If not, argue in a few sentences why it would not work.

2. Do problem 15.2-3. Juan will give an example of using a proof by substitution for a lower bound in Section on Friday.

3. Here is a simpler version of problem 15-3. We want to figure out the minimum cost required to transform a string x into another string y. We work from left to right, maintaining a pointer i into the input string X and a pointer j into the output string Y. Initially i=j=0. There are four operations allowed:

• Copy: copy character x[i] to y[j]; i++; j++;
• Replace: write any character you like as y[j]; i++; j++;
• Delete: (skips a character of X) i++;
• Insert: write any character you like as y[j]; j++;

• Copy - 0
• Replace - 1
• Delete - 1
• Insert - 1