Given two sequences stem:$[$x$[1$:m$\backslash ]]$ and stem:$[$y$[1$:n$\backslash ]]$ and the costs of the

transformation operations, the $*$edit distance$*$ from stem:$[$x$]$ to stem:$[$y$]$ is the

cost of the least expensive operation sequence that transforms stem:$[$x$]$ to

stem:$[$y$].$ Describe a dynamic$-$programming algorithm that finds the edit

distance from stem:$[$x$[1$:m$\backslash ]]$ to stem:$[$y$[1$:n$\backslash ]]$ and prints an optimal operation

sequence.

In doing this, you are going to be arguing that this problem exhibits

optimal substructure $($step $1),$ providing a recurive solution $($step $2),$ giving

pseudocode for computing the edit distance $($step $3),$ and giving pseudocode for

constructing the optimal operation sequence based on the edit distance $($step $4).$

Analyze the running time and space requirements of your algorithm.