##### Differences

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