Given two sequences x[1..m]x[1..m] and y[1..n]y[1..n] and set of transformation-operation costs, the edit distance from xx to yy is the cost of the least expensive operation sequence that transforms xx to yy. Describe a dynamic-programming algorithm that finds the edit distance from x[1..m]x[1..m] to y[1..n]y[1..n] and prints an optimal operation sequence. Analyze the running time and space requirements of your algorithm.