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

cs-312:hw18 [2014/12/31 23:04] ringger created |
cs-312:hw18 [2014/12/31 23:23] (current) ringger |
||
---|---|---|---|

Line 12: | Line 12: | ||

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) | 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 <math>x=(A,Z,C,D,E,F)</math> and <math>y=(R,S,A,Z,T,Q,D)</math>, the sub-sequence <math>(A,Z,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,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. |

===Question 2=== | ===Question 2=== | ||

- | 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: <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>. 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. | + | 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. |

===Question 3=== | ===Question 3=== |