Assignment 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 are not allowed to modify any of the code in provided files MSR.py and myMSRClasses.py. When modifying file myMSRFunctions.template to create myMSRFunctions.py, you cannot:

• 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).

Violations of any of these constraints will result in severe mark deductions (see assignment evaluation scheme below).

Hints

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

Assignment Submission

Please submit your program file myMSRFunctions.py through the course D2L / Brightspace shell by 11:59pm on the assignment due date. Note that each program file must have the following comment block at the top, where the X's are replaced with the appropriate information. For example, my Python program for this assignment would begin with the following comment block:

#########################################################
##  CS 3600 (Winter 2025), Assignment #2               ##
##   Script File Name: myMSRFunctions.py               ##
##       Student Name: Todd Wareham                    ##
##         Login Name: harold                          ##
##              MUN #: 8008765                         ##
#########################################################

You do not have to develop your code on our CS departmental systems. However, as your code will be compiled and tested on our CS departmental systems as part of the assignment marking process, you should ensure that your code compiles and runs correctly on at least one of these systems.

Additional Notes:

• Mar 5, 2025
  Error in description of assignment of backpointer codes in value ties fixed.

• Dec 11, 2024
  Assignment #2 posted.

Created: December 11, 2024
Last Modified: March 6, 2024