Programming Problem #2

Consider the following problem: given two character strings s1 and s2, an optimal Maximally-Similar Region (MSR) of s1 and s2 is two substrings of s1 and s2 (with possible embedded "skip" characters ("-")) that has the maximum summed score over some character-pair matching function match(c1,c1). For example, if s1 and s2 are lower-case alphabetic strings, a useful matching function is

                { 1.0     if c1 == c2
match(c1, c2) = { 0.5     if c1 and c2 are both vowels
                { 0.25    if c1 and c2 are both consonants
                { -0.75   otherwise

For integers 0 <= i <= |s1| and 0 <= j <= |s2|, let M[i,j] be the value of the optimal MSR of the first i characters of s1 and the first j characters of s2. Given such a function and (|s1| + 1) x (|s2| + 1) value and |s1| x |s2| backpointer matrices M and B such that M[i,j] = 0.0 when either i or j is zero, M[i,j] and B[i,j] are computed by the following recurrences:

  
            { M[i,j-1] - 0.25                    character j in s2 is skipped
            {                                     (option 1)
M[i,j] = max{ M[i-1,j-1] + match(s1[i],s2[j])    the ith character in s1 matches
            {                                     the jth character in s2 
            {                                     (option 2)
            { M[i-1,j] - 0.25                    character i in s1 is skipped
            {                                     (option 3)
            { 0.0                                otherwise (option 0)

  
           { 1   if option 1 was invoked to compute M[i,j]
B[i,j] =   { 2   if option 2 was invoked to compute M[i,j]
           { 3   if option 3 was invoked to compute M[i,j]
           { 0   otherwise

The above assumes that there are no ties in computing the maximum value for M[i,j]; if there is a tie involving any of options 1, 2, and 3, the lowest of these involved option-numbers is used to compute B[i,j], e.g., see cells M[13,1] and B[13,1] in Test #10 in the provided output which involve a tie between options 0 and 3 and select option 3. Once M and B are filled in using these recurrences, traceback to compute an optimal MSR is initiated from the square in M with the maximum value and terminates when it reaches an M-square with value 0.0. If there are multiple squares in M with the same maximum value, traceback starts from the maximum-value square encountered first in a left-right search starting at row 0 and progressing upwards in M. For example, given the matching function and recurrences described above, the optimal MSR computed for s1 = aoca and s2 = oca (Test #1 below) is

oca
oca

and the optimal MSR computed for s1 = acoa and s2 = aoca (Test #2 below) is

aco-a
a-oca

Write and document a Python program that, given two lower-case alphabetic strings s1 and s2, uses the dynamic programming algorithm described above to compute and output an optimal maximally-similar region of s1 and s2. You have been given Python files myMSRClasses.py and MSR.py and you need to fill in the function definitions in file myMSRFunctions.template according to the dynamic programming algorithm described above create a file myMSRFunctions.py such that MSR.py (when run relative to given problem-description files str1.txt, str2.txt, str3.txt, str4.txt, str5.txt, str6.txt, str7.txt, str8.txt, str9.txt, and str10.txt using python3 on the CS departmental LabNet systems) can exactly reproduce the outputs in script file out.script.

You should not modify any of the code in provided files MSR.py and myMSRClasses.py. When modifying file myMSRFunctions.template to create myMSRFunctions.py, try not to:

• modify the given import statement;
• add other import statements (this includes import statements added automatically by IDEs such as PyCharm);
• add, modify, or remove function definitions;
• add new class definitions or global variables (use the provided classes in file myMSRClasses.py); or
• access any provided class attributes directly (use provided attribute access functions in file myMSRClasses.py).

Hints

You may find it useful to progress through the given tests in the given order when debugging your code.

Additional Notes:

• July 15, 2026
  Programming Problem #2 posted.

Created: July 15, 2026
Last Modified: July 15, 2026