Homework Assignment #18

To apply dynamic programming to a new problem: the longest common subsequence problem.

Show all work neatly.

Solve problem 6.11 in the textbook using the first four steps of our 6-step process of Dynamic Programming. Show each step. (3 points each)

Note that a common sub-sequence need not be contiguous. e.g., for $x=(A,Z,C,D,E,F)$ and $y=(R,S,A,Z,T,Q,D)$, the sub-sequence $(A,Z,D)$ occurs in both and is therefore common, even though its members are not contiguous. It is also the longest such sub-sequence.

Use your solution from question (1) to show step 5 and step 6 (3 points each) of the DP process to solve the following longest common sub-sequence instance: $x=(p,s,e,u,d,o,p,o,l,y,n,o,m,i,a,l)$ and $y=(p,n,e,u,m,a,t,i,c)$. For step #5, show your completed table, and report the length of the longest common sub-sequence. Also show how to keep suitable back-pointers. For step #6, extract the two optimal sub-sequences using the back-pointers.

More fun: Place the answers from question (2) in order according to which one would come first in the dictionary. Take the first one and remove the 'e'. Translate it from Spanish into English. Go, Cougars!