Given two strings $a_1{a}_{2}dots{a}_n$ and $b_1{b}_{2}dots{b}_m,$ 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 $a_1{a}_{2}dots{a}_k$ and $b_1{b}_{2}dots{b}_l$ by a function name.

$($b$)$ Every function has variable$($s$).$ Now, it is time to decide on them, by which you can narrow down the

problem into sub$-$problems. Although they may seem straightforward, they can be tricky. The function's

variables usually correspond to the indices and$/$or capacities that make it easier to construct smaller sub$-$

problems. For example, the matrix indices in the Matrix chain Multiplication, the index of the last item we

consider and the weight capacity in the Knapsack, or the lengths of the two sequences in Longest Common

Subsequence etc. As an example, however, there are no variables related to the three possible weights $($i$.$e$.$

$1,4,5$ but only the weight capacity in the unbounded Knapsack because the weights are constants given

to the problem. Write down the variables of your function in between parenthesis and define what your

function represents as complete and concise as possible in only one sentence, as we did in class $($e$.$g$.$ Given a

string $x_i$ of length i and another string $Y_j$ of length $j,c(i,j)$ represented the length of their longest common

subsequence in the longest Common Subsequence problem.$)$

NameOfYourFunction$(.....)$

$($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 $\text{'}.\text{'}.$

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 $3^{rd}$

scenario has two subcases:

cdotscdots,$a_k$

cdotscdots,$b_1$

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 $\text{'}.\text{'}$ 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 $(dotsdots)=$dotsdots

$($d$)$ In the second scenario, assume that the edit distance is minimized if only you don't put any of the second

string's letters, but just put a $\text{'}.\text{'}$ for the second string and put the first 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 second 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 second scenario.

NameOfYourFunction $(dotsdots)=$dotsdots

$($e$)$ In the third scenario, assume that the edit distance is minimized if only you put the last letters from both

strings. 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 third scenario, the right$-$hand side

would be some function of the function you have written for the corresponding sub$-$problem. This function

has two legs: the one where the last letters are not the same, and the one where the last letters are not the

same. Write down the right$-$hand side for the third scenario.

NameOfYourFunction $(dotsdots)=$dotsdots

$($f$)$ Actually, we do not do any choice in dynamic programming. What we must do is first to consider all

possibilities like above and choose the minimum of those right$-$hand sides. Now you are ready to minimize

them. Write down the whole formulation which collects all the above right$-$hand side functions into one as

a minimization function.