Assignment 2

Question 1

Given two strings s1 and s2, a string x is a sub(str/seq) of s1 and s2 if x is a substring of s1 (s2) and a subsequence of s2 (s1). For example, two sub(str/seq)s of the strings s1 = "abort" and s2 = "stabagot" are "abo" (substring of s1, subsequence of s2) and "ot" (subsequence of s1, substring of s2).

Write and document a Python program that, given two strings specified in a file that is input as a command-line argument, uses dynamic programming to find the length of the longest sub(str/seq) of those strings and returns one of those longest sub(str/seq)s. An example input file str1.dat is as follows:

stabagot
abort

Examples of several program runs relative to the item-subset set files str1.dat, str2.dat, str3.dat, str4.dat, str5.dat, and str6.dat are given in script file out.script. It is these results that your program should be able to replicate. ,

Hints

You may find it useful to modify the dynamic programming algorithm given in class for the Longest Common Subsequence problem. In particular, think about the different roles of horizontal and vertical backpointers when revising the LCS recurrence and consider broadening the region of the DP table from which traceback can start to obtain an optimal solution.

Assignment Submission

Please submit your program files for Q1 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 Question #1 of this assignment would begin with the following comment block:

#########################################################
##  CS 3600 (Winter 2024), Assignment #2, Question #1  ##
##   Script File Name: LSSS.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:

• Nov 21, 2023
  Assignment #2 posted.

Created: November 21, 2023
Last Modified: February 12, 2024