subject
Engineering, 13.11.2019 01:31 chloeholt123

Given two strings x = x1, and y = y1, give a dynamic programming algorithm to find the length k of the longest string z = z1, . . , zk where z appears as a substring of x and as a subsequence of y . recall, a substring means consecutive elements. for example, for the following input: x = a, b,d, b,a, b,f, g,d y = b, e,t, f,d, b,f, a,f, r then the answer is 4 (since, b, d, b, a is a substring of x and it is also a subsequence of y). you do not need to output the actual substring, just its length. (faster (and correct) in asymptotic o(·) notation is worth more credit.) (a) define the entries of your table in words. e. g., t (i) or t (i, j) is (b) state recurrence for entries of table in terms of smaller subproblems. (c) write pseudocode for your algorithm to solve this problem. (d) analyze the running time of your algorithm.

ansver
Answers: 3

Other questions on the subject: Engineering

image
Engineering, 04.07.2019 18:10, bunnles
During a steady flow process, the change of energy with respect to time is zero. a)- true b)- false
Answers: 2
image
Engineering, 04.07.2019 18:10, Tyrant4life
Draw the engineering stress-strain curve for (a) bcc; (b) fcc metals and mark important points.
Answers: 1
image
Engineering, 04.07.2019 18:20, luisgonz5050
Find the kinematic pressure of 160kpa. for air, r-287 j/ kg k. and hair al viscosity of air at a temperature of 50°c and an absolute (10 points) (b) find the dynamic viscosity of air at 110 °c. sutherland constant for air is 111k
Answers: 3
image
Engineering, 04.07.2019 19:10, Calliedevore
The proportional limit is always greater than the yield strength for a material. a)-trune b)- false
Answers: 3
You know the right answer?
Given two strings x = x1, and y = y1, give a dynamic programming algorithm to find the length k of t...

Questions in other subjects: