From Mohammed J. Zaki

IntroAlgorithms: Lab7

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'

Retrieved from http://www.cs.rpi.edu/~zaki/www-new/pmwiki.php/IntroAlgorithms/Lab7
Page last modified on April 12, 2018, at 04:16 PM