On a string s, we have the following elementary operations: i) Insertion of a single letter into the string s, e.g., BT ? BAT. ii) Deletion of a single letter in the string s, e.g., CAT E ? CAT. iii) Substitution of one letter in the string s by another one, e.g., BAT ? CAT. The Levenshtein distance D(s, t) between two strings s and t is equal to the smallest number of operations i), ii), or iii) to transform the string s into t. Let m denote an array where the entry m[i, j] contains the Levenshtein distance of the initial segments s[1..i] and t[1..j] of the strings s and t, respectively. (a) Determine the entries and justify your claim:
(a) m[i, 0] =
(b) m[0, j] =
(b) The following facts are easily established: (F1) If we can transform s[1..i] to t[1..j - 1] in k operations, then we can simply add t[j] afterwards to get t[1..j] in k + 1 operations. (F2) If we can transform s[1..i - 1] to t[1..j] in k operations, then we can do the same operations on s[1..i] and then remove the original s[i] at the end in k + 1 operations. (F3) If we can transform s[1..i - 1] to t[1..j - 1] in k operations, we can do the same to s[1..i] and then do a substitution of t[j] for the original s[i] at the end if necessary, requiring k or k + 1 operations. These three facts suffice to determine the value of m[i, j] from the entries m[i, j - 1], m[i - 1, j], and m[i - 1, j - 1]. Derive the formula for m[i, j] and justify your result. Explain how the two subcases in F3 are resolved.
m[i, j] =
(c) What is the complexity of any dynamic programming approach based on parts a) and b), assume that s and t are of length a and b. Use Big Omega notation