Python 3 Only

Problem 1. (Calculating Edit Distance Using Dynamic Programming) A direct implementation of the above recursive scheme will work, but it is spectacularly inecient. If both input strings have N characters, then the number of recursive calls will exceed 2N. To overcome this performance bug, we use dynamic programming. Dynamic programming is a powerful algorithmic paradigm, rst introduced by Bellman in the context of operations research, and then applied to the alignment of biological sequences by Needleman and Wunsch. Dynamic programming now plays the leading role in many computational problems, including control theory, nancial engineering, and bioinformatics, including BLAST (the sequence alignment program almost universally used by molecular biologists in their experimental work). The key idea of dynamic programming is to break up a large computational problem into smaller subproblems, store the answers to those smaller subproblems, and, eventually, use the stored answers to solve the original problem. This avoids recomputing the same quantity over and over again. Instead of using recursion, use a nested loop that calculates opt[i][j] in the right order so that opt[i + 1][j + 1], opt[i + 1][j], and opt[i][j + 1] are all computed before we try to compute opt[i][j].

Write a program edit_distance.py that reads strings x and y from standard input and computes the edit-distance matrix opt as described above. The program should output x, y, the dimensions (number of rows and columns) of opt, and opt itself, using the following format: The rst and second lines should contain the strings x and y. The third line should contain the dimensions of the opt matrix, separated by a space. The following lines should contain the rows of the opt matrix, each ending in a newline character. Use stdio.writef() with the format string %3d to write out the elements of the matrix.

$ python3 edit_distance.py < data/example10.txt

AACAGTTACC

TAAGGTCA

11 9

7 8 10 12 13 15 16 18 20

6 6 8 10 11 13 14 16 18

6 5 6 8 9 11 12 14 16

7 5 4 6 7 9 11 12 14

9 7 5 4 5 7 9 10 12

8 8 6 4 4 5 7 8 10

9 8 7 5 3 3 5 6 8

11 9 7 6 4 2 3 4 6

13 11 9 7 5 3 1 3 4

14 12 10 8 6 4 2 1 2

16 14 12 10 8 6 4 2 0