1. Given two strings a1a2an and b1b2bm, find their minimum edit distance. The edit distance is the number of mismatches in an alignment. For example, the minimum edit distance between the two strings "SUNNY" and "SNOWY" in the following alignment is 3 : Likewise, the minimum edit distance between "INTENTION" and "EXECUTION" is 5. (a) Represent the minimum edit distance between a1a2ak and b1b2bl by a function name. (c) We can start writing the right-hand side of the formulation in a recursive manner. Now spend a considerable amount of time to imagine how would an optimal alignment would look like for two arbitrary strings. Yes, it is actually two strings that are placed one above the other and expanded at some locations with a ' ." Consider the last choice you would do to obtain this imaginative optimal solution. Yes, you are right! You must choose what to put as two last characters. Here, there can be three different scenarios, where the 3rd scenario has two subcases: (1) (2) (3) ak b1 In the first scenario, assume that the edit distance is minimized if only you don't put any of the first string's letters, but just put a 'for the first string and put the second string's last letter. Given this assumption, write down the sub-problem you must solve (i.e. the same function with slightly different variables). Then, if the last alignment was as in the first scenario, the right-hand side would be some function of the function you have written for the corresponding sub-problem. Write down the right-hand side for the first scenario. NameOfYourFunction ()=