P1

Consider the Longest Common Subsequence (LCS) from the notes. We phrased the solving of this problem as a sequence of choices: add&chop, chop-X and chop-Y. I stated that no greedy choice works for this. Find counterexamples for the following two greedy choice strategies:
  1. Strategy 1: choose add&chop if the last letters of X and Y are equal, and otherwise chose to chop whichever of X and Y is longer.

  2. Strategy 2: choose add&chop if the last letters of X and Y are equal, and otherwise
    • set S to the set of letters appearing in both X and Y
    • set dX to the number of chop-X's needed to get to where the last character of X is an element of S
    • set dY to the number of chop-Y's needed to get to where the last character of Y is an element of S
    • if dX < dY choose chop-Y else choose chop-X

P2

Consider the LCS memoized and dynamic programming algorithms from the lecture notes. They create a table E with 1's for add&chop, 2's for chop-X and 3's for chop-Y. Below is the table E produced for input 
X := fortunefavors
Y := effortrewards
Using the table, recover the longest common subsequence.
E012345678910111213
0-1-1-1-1-1-1-1-1-1-1-1-1-1-1
1-12113333333333
2-12221333333333
3-12222131333133
4-12222213333333
5-12222222222222
6-12222222222222
7-11222222133333
8-12112222222222
9-12222222221333
10-12222222222222
11-12221222222222
12-12222121222133
13-12222222222221