Consider the edit distance problem: you are provided with two strings X and Y of lengths m and n respectively. We are interested in the basic (so-called Levenshtein) distance; insertions and deletions each have a cost of 1, mismatches have a cost of 1 and matches have a cost of 0. Let ? be the optimal edit distance between X and Y . Derive a dynamic program to compute the number of optimal alignments of X and Y (i.e. the total number of alignments between X and Y that induce an edit distance of ?). Describe why your algorithm works. Your algorithm should use O(mn) time and space.