For the algorithm we also need to prove the correctness and the time complexity

Question 2. (15 points) We gave in class an O(mn) time algorithm for computing the edit distance d(A,B) from a string A=a1a2am of length m to a string B=b1b2bn of length n, as the least-cost sequence of insertions, deletions, and substitutions for transforming A into B. Recall that, in that algorithm, I(x) was the cost of inserting symbol x,D(x) was the cost of deleting x, and S(x,y) was the cost of replacing x with y. We refer to the tables I,D,S as the cost tables. 1 1. (5 points) Give an example of an A,B, and cost tables showing that it is possible to have d(A,B)=d(B,A) even when all insertions and deletions have the same cost (independent of what symbol is being inserted or deleted, i.e., for all x,y we have I(x)=D(x)=I(y)= D(y)) 2. (5 points) Give an example of an A,B, and cost tables showing that it is possible to have d(A,B)=d(B,A) even when the S table is symmetric (i.e., when S(x,y)=S(y,x) for all x,y). 3. (5 points) Suppose that m=n, that the alphabet consists of integers, and that no insertions are allowed, no deletions are allowed, and the cost S(x,y) of a substitution is xy. Give an O(n) time algorithm for computing d(A,B) in this special case