This shows you the differences between two versions of the page.

cs-312:hw19 [2014/12/31 16:05] ringger created |
cs-312:hw19 [2014/12/31 16:24] (current) ringger |
||
---|---|---|---|

Line 8: | Line 8: | ||

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. | 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 <math>x=(A,B,C,D,E,F)</math> and <math>y=(R,S,A,B,T,Q,D)</math>, the sub-sequence <math>(A,B,D)</math> occurs in both and is therefore common, even though its members are not contiguous. It is also the longest such sub-sequence. | + | 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:''' | '''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: <math>x=(p,s,e,u,d,o,p,o,l,y,n,o,m,i,a,l)</math> and <math>y=(p,n,e,u,m,a,t,i,c)</math>. Report the length of the longest common sub-sequence as well as the sub-sequence itself. | + | 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:''' | '''Question 3:''' |