Do problem 15-5(a) (Edit Distance) on page 406 in the book, but omit the kill operation. Note that the definition of edit distance in this problem is not the same as the definition used in class.
This is a dynamic programming problem. It is not enough to produce an algorithm. If you provide only an algorithm, you will receive no credit. You must go through the steps of a dynamic programming algorithm. Define the subproblems that you will solve. Write recurrences that relate solutions to subproblems. Say how to compute all of the solutions to the subproblems. Say how to write out the sequence of operations to use. (Just show the operations, as shown in the left-hand column of the example that converts "algorithm" to "altruistic".)