Lab 7: Edit Distance, Due Wed Apr 18, during Lab

In this lab you will implement the dynamic programming algorithm to compute the edit distance between two strings, as given in Section 6.3.

Your program should input two strings $$X$$ and $$Y$$ and print the edit distance between them, as well as the alignment of the two strings.

For example, given $$X$$ = EXPONENTIAL and $$Y$$ = POLYNOMIAL, the output should be:
edit distance = 6
alignment:
EXPONEN-TIAL
--POLYNOMIAL

Report your output on the following strings:
$$X$$ = 'CATAAGCTTCTGACTCTTACCTCCCTCTCTCCTACTCCTGCTCGCATCTGCTATAGTGGAGGCCGGAGCAGGAACAGGTTGAACAG'
$$Y$$ = 'CGTAGCTTTTTGGTTAATTCCTCCTTCAGGTTTGATGTTGGTAGCAAGCTATTTTGTTGAGGGTGCTGCTCAGGCTGGATGGA'