Given two strings A and B, we can transform A to B using insertions, deletions, and substitutions. Each of these operations comes with a prespecified cost. Our goal is to determine the minimum cost of changing A to B. We call this cost the edit distance from A to B. For example, suppose A= "ataccg" and B= "aacgca" and insertions, deletions, and substitutions all have cost 1 . Then we can transform A to B by (1) deleting the t,(2) inserting a g between the two c 's, and (3) substituting the last g for an a. This process has total cost 3 and the edit distance from A to B is 3 . We can represent this transformation with the following alignment: ABaataaccgccga Here, insertions are represented by an underscore ( " ") in A, deletions are represented by an underscore in B, and substitutions are represented by mismatched characters. (a) (5 pts) Determine the edit distance and an optimal alignment between the strings "exponential" and "polynomial". Show your work (draw a filled in table and the resulting alignment). (b) (15 pts) Describe the optimal substructure of this problem. In particular, define the edit distance between A and B in terms of the solution for shorter strings. Justify your answer. (c) (10 pts) Write pseudocode for a function editDistance (A, B, ins, del, sub) which returns the edit distance between A and B given costs for insertions, deletions, and substitutions. Assume that matches have a cost of 0 . This function does not need to generate an alignment. (d) (5 pts) Analyze the asymptotic run time of your algorithm