The edit distance between two strings S_1 and S_2 is the minimum number of operations to convert one string to the other string. We assume that three types of operations can be used: Insert (a character), Delete (a character), and Replace (a character by another character). For example, the edit distance between dof and dog is 1 (one Replace), between cat and act is 2 (one Delete and one Insert or two Replace), between cat and dog is 3 (3 Replace). Design a dynamic programming algorithm to compute the edit distance between two strings by following the steps below: Write down the principle of optimality for the minimum edit distance problem, and prove that the problem satisfies the principle of optimality. Show the recurrence equation for computing the edit distance. Provide pesudocode for Edit-Distance(S_1, S_2). Use Edit-Distance() to create the table d(d[i,j] is defined above) for S_1=cats and S_2=fast. The entry at d[4, 4] should show the correct edit distance between the two words. The edit distance between two strings S_1 and S_2 is the minimum number of operations to convert one string to the other string. We assume that three types of operations can be used: Insert (a character), Delete (a character), and Replace (a character by another character). For example, the edit distance between dof and dog is 1 (one Replace), between cat and act is 2 (one Delete and one Insert or two Replace), between cat and dog is 3 (3 Replace). Design a dynamic programming algorithm to compute the edit distance between two strings by following the steps below: Write down the principle of optimality for the minimum edit distance problem, and prove that the problem satisfies the principle of optimality. Show the recurrence equation for computing the edit distance. Provide pesudocode for Edit-Distance(S_1, S_2). Use Edit-Distance() to create the table d(d[i,j] is defined above) for S_1=cats and S_2=fast. The entry at d[4, 4] should show the correct edit distance between the two words