Technology: Python, Visual Studio Code

Question 1

This algorithm find the longest common substring between two input strings using recursion.
This method uses a top-down recursive approach with a cache to store previously calculated results
from the recursive calls. The lecture slide below graphically shows the steps of the algorithms.

q1.py (click on image to download code):

Question 2

This algorithm is similar to the last but it uses a bottom-up approach instead. It first
fills a table with the lengths all combinations of the longest common substrings. Then it
retrieves the answer by back-tracing through the table with the findResult() function.

q2.py (click on image to download code):

Question 3

The scenario for this problem is that there are two versions of text with multiple lines
and the differences between them need to be tracked. For each line, the algorithm outputs a 'T' for
transfer, 'D' for delete, 'I' for insert and 'S' for substitution. Following the letter is the older
version of the line. Following this is the new version of the line. The algorithm finds the edit
distance between the two versions.

q3.py (click on image to download code):

Question 4

This problem uses the answer from the previous and the longest common substring algorithm.
The output is the same as the last problem except it uses double brackets to signify character
changes within each line on substitutions.

q4.py (click on image to download code):