Homework Assignment #19

Show all work neatly.

Question 1:

Solve problem 6.11 in the textbook using the first four steps of our 6-step process of Dynamic Programming. Show each step. In particular, for step #6, show how to keep suitable back-pointers.

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

Question 2:

Use your solution from part (1) to show step 5 and step 6 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)$. Report the length of the longest common sub-sequence as well as the sub-sequence itself.

Question 3:

Extra fun: Take your answer from part (2), remove the 'e' and translate from Spanish into English. Go, Cougars!