Question

3. The following equation describes the recurrence underlying our dynamic pro-gramming algorithm for EDIT DISTANCE for the case of operations COPY (cost0), INSERT (cost 2), DELETE (cost 2) and REPLACE (cost 3). Here, as in the course, c[i, j] describes entry (1,5) of the dynamic programming table, ™, is character number of the input string and y; is character number of the output string,1

0 & \text { if } i=0 \text { and } j=0 \\

c[i-1, j-1] & \text { if } i>0, j>0 \text { and } x_{i}= \\

3+c[i-1, j-1] & \text { if } i>0 \text { and } j>0 \\

2+c[i-1, j] & \text { if } i>0 \\

2+c[i, j-1] & \text { if } j>0

\end{array}\right. Describe a modification of the equation to incorporate the following operation: • TRIPLE: if the input contains three identical characters in a row, you may delete one of them at cost 1. For example, the edit distance from "mottto" to "motto" would be 1, while the distance from "motto" to "moto" would be 2. Also describe what effect this modification has on the running time.[10 marks]

Fig: 1

Fig: 2

Fig: 3

Fig: 4

Fig: 5