Homework answers / question archive / Dynamic Programming: String Matching] Use dynamic programming technique to find least-cost alignment of the two strings MARS and CAAS under the operation cost model where insert and delete cost +1, substitute costs +2 and match costs -2

Dynamic Programming: String Matching] Use dynamic programming technique to find least-cost alignment of the two strings MARS and CAAS under the operation cost model where insert and delete cost +1, substitute costs +2 and match costs -2

Computer Science

Share With

Dynamic Programming: String Matching]

Use dynamic programming technique to find least-cost alignment of the two strings MARS and CAAS under the operation cost model where insert and delete cost +1, substitute costs +2 and match costs -2. Clearly state (i) the recurrence relation and then (ii) fill the appropriate table given on the next page, and show the least-cost alignment (cost plus properly aligned strings) on this page below?  (There is a third part of the question on the next page.)

(i) RECURRENCE RELATION WITH BOUNDARY CONDITIONS AND COST MODEL INCORPORATED:

 (ii) RESULT à   MINIMUM COST AND ALIGNMENT:

USE THE ABOVE TABLE AS TEMPORARY SCRIBBLE SPACE.

(ii)

WRITE THE FINAL TABLE BELOW (COPY COST AND ALIGNMENT TO THE PREVIOUS PAGE):

(iii) Is the least-cost alignment unique?     CIRCLE ONE OF:       YES         NO

(iv) Write a string matching program that takes two strings and outputs least cost alignment that shows the least cost and the required transformation. Use the recurrence to define the logic and the above manually generated example solution to test it. While I am not specifying the input carefully and leaving it to your discretion, make sure you use a form that enables you to run it on different test cases.