##### Differences

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 2014/12/31 23:23 ringger 2014/12/31 23:04 ringger created 2014/12/31 23:23 ringger 2014/12/31 23:04 ringger created 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) ​and <​math>​y=(R,​S,​A,​Z,​T,​Q,​D)​, the sub-sequence ​<​math>​(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. + 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) ​and <​math>​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. + 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===