Consider a variation on the edit-distance problem we discussed in class. Our ori
ID: 3852379 • Letter: C
Question
Consider a variation on the edit-distance problem we discussed in class. Our original problem considered the operations of insert, delete, and replace to be equivalent in terms of cost. Now, re-cast the problem of edit distance as transforming string x into string y with our three operations and the following costs: Delete: $3 Insert: $4 Replace: $5 We still want to transform x into y while minimizing the total cost. Recall that our original solution had the following recurrence, excluding the base case: c[i,j] = c[i-1,j-1] if xi = yj minimum(c[i-1, j-1], c[i-1,j], c[i,j-1]) +1 otherwise Would this recurrence produce an optimal solution for the new version of the problem? Justify your answer.
Explanation / Answer
NO, The older recurrance would not give the correct answer as in that recurrance, We have assumed that the cost for all the operations - Insertion, Deletion and Modification is the same, i.e. $1.
In this case, we have 3 different costs for all 3 operations so although the state-transitions for the operations would be the same, the cost for each transition would be different. Hence, a new recurrance will be formed.
The base case would be same, however as if the xi == yj, then the cost of editing this letter is 0.
Now the cost for three operations with their states :
The new recurrance would be as follows: