Question

Given strings X=x

1
​
x
2
​
…x
n
​
and Y=y
1
​
y
2
​
…y
m
​
, composed of symbols from a given alphabet, the objective is to transform X into Y using a minimum cost sequence of edi operations. The edit operations and associated costs are: - delete symbol x
i
​
from X, at costD(x
i
​
); - insert symbol y
j
​
into X, at cost l(y
j
​
); - change symbol x
i
​
from X into y
j
​
, at costC(x
i
​
). The cost of a sequence of edit operations is the sum of the costs for all individual symbols. Example: Let X=x
1
​
x
2
​
x
3
​
x
4
​
x
5
​
=aabab,Y=y
1
​
y
2
​
y
3
​
y
4
​
=babb, and the costs for deletion, insertion and change are 1,1 , and 2 , respectively. Different sequences for transforming X into Y are: (i) delete all symbols of X, then insert all symbols of Y one by one (at total cost 5+4=9 ); (ii) delete x
1
​
and x
2
​
yielding X=bab and insert y
4
​
=b at the end (at cost 1+1+1=3) (iii) change x
1
​
to y
1
​
yielding X= babab and then delete x
4
​
=a (at cost 2+1=3 ). 1. For the example in the slides, X=aabab, and Y=babb, use the costs of 0.5,0.4, and 1.2 for I (Insert), D (Delete), and C (Change), respectively. In the algorithm, C(xi,yj) is applied with its assigned cost if xi is not equal to yj; if xi equals yj then the cost C(xi,yj)=0. Give matrix, cost, and editing sequence. Show and explain all steps. 1b. Give the string editing algorithm pseudocode that returns the cost matrix and cost. 1c. Give pseudocode for the modified algorithm that also produces the decision sequence of I/D/C to transform X into Y; determine the algorithm's time complexity. The algorithms should compute the cost table, and final cost(n,m), and the modified algorithm should also generate the decision sequence.

Answer 1

C(xi, yj) is the cost of changing symbol xi from X into symbol yj from Y. In this example, the costs for I, D, and C are given as 0.5, 0.4, and 1.2, respectively. Therefore, to find the cost of changing a symbol xi from X into symbol yj from Y, we can use the following formula:

C(xi, yj) = 0.4 if xi = yj

C(xi, yj) = 1.2 if xi ≠ yj

For example, to change the first symbol of X (which is 'a') into the first symbol of Y (which is 'b'), we have xi = 'a' and yj = 'b'. Since xi ≠ yj, the cost of this operation is C(xi, yj) = 1.2. Similarly, to change the second symbol of X (which is 'a') into the third symbol of Y (which is 'b'), we have xi = 'a' and yj = 'b'. Since xi ≠ yj, the cost of this operation is also C(xi, yj) = 1.2.