Differences

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

Link to this comparison view

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===
cs-312/hw18.txt ยท Last modified: 2014/12/31 23:23 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