Algorithm: Weighted Interval Scheduling & Dynamic Programming (Knapsack, Edit Distance)
Give an algorithm in pseudocode that will produce the minimal-cost sequence of edit operations for strings u and v from the array C computed by following algorithm (in picture). Give proofs of correctness and running time for your algorithm.
(Given 2 strings u = a1..am and v = b1..bn, find edit distance d(u,v)
![1. procedure DISTANCE(u = a1 ·..am, V= b1 · . - bn,d)<br>2. C[0, 0] +0<br>3.<br>for i from 1 to m do<br>C[i, 0] + d(ai, e) + C[i – 1,0]<br>for j from 1 to n do<br>C[0, j] + d(e,b;) + C[0, j – 1]<br>4.<br>5.<br>6.<br>7.<br>for i from 1 to m do<br>for j from 1 to n do<br>C[i, j] - min{d(a;, b;) + C[i – 1, j – 1], d(a;, e) + C[i – 1,j], d(ɛ, b;) + C[i, j – 1]}<br>return C[m, n]<br>8.<br>9.<br>10.<br>](https://s3.us-east-1.amazonaws.com/storage.unifolks.com/qimg-008/008_mwbbzz0-vngk3r3a.png)
Extracted text: 1. procedure DISTANCE(u = a1 ·..am, V= b1 · . - bn,d) 2. C[0, 0] +0 3. for i from 1 to m do C[i, 0] + d(ai, e) + C[i – 1,0] for j from 1 to n do C[0, j] + d(e,b;) + C[0, j – 1] 4. 5. 6. 7. for i from 1 to m do for j from 1 to n do C[i, j] - min{d(a;, b;) + C[i – 1, j – 1], d(a;, e) + C[i – 1,j], d(ɛ, b;) + C[i, j – 1]} return C[m, n] 8. 9. 10.