Differences

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

Link to this comparison view

cs-312:hw19 [2014/12/31 23:05]
ringger created
cs-312:hw19 [2014/12/31 23: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:'''​
cs-312/hw19.txt ยท Last modified: 2014/12/31 23:24 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0