Give a sequence X = (x1, x2,..., m) and another sequence Y = (y1, 92, ...,...

 

Transcribed Image Text:

Give a sequence X = (x1, x2,..., m) and another sequence Y = (y1, 92, ..., Ym), the Edit Distance is a difference or distance, d, between two sequences. Consider the following recurrence relation that generates the optimal distance for the Edit Distance problem: d[ij]= di-1, j] +1 min d[i, j-1]+1 otherwise. di-1, j-1]+k if j = 0. if i = 0. (1) where k = 0, if x = yj, 1 otherwise. Hint: You do not need to understand the Edit Distance problem domain to work the following problems. a. Write a recursive procedure ED (exponential time algorithm) which solves this recurrence relation. b. Write a top-down memoized version of ED procedure you wrote previously. Your procedure should run in (mn) time. You will need to create two procedures. The first procedure will declare and initialize a memo array, d[i, j], with a sentinel value -1, then make the initial call to the second procedure. Give a sequence X = (x1, x2,..., m) and another sequence Y = (y1, 92, ..., Ym), the Edit Distance is a difference or distance, d, between two sequences. Consider the following recurrence relation that generates the optimal distance for the Edit Distance problem: d[ij]= di-1, j] +1 min d[i, j-1]+1 otherwise. di-1, j-1]+k if j = 0. if i = 0. (1) where k = 0, if x = yj, 1 otherwise. Hint: You do not need to understand the Edit Distance problem domain to work the following problems. a. Write a recursive procedure ED (exponential time algorithm) which solves this recurrence relation. b. Write a top-down memoized version of ED procedure you wrote previously. Your procedure should run in (mn) time. You will need to create two procedures. The first procedure will declare and initialize a memo array, d[i, j], with a sentinel value -1, then make the initial call to the second procedure.