Assignment 1

Consider the following problem:
Set Cover
Input: A set I = {i1, i2, ..., in} of elements and a set S = {s1, s2, ..., sm} of subsets of I.
Output: All minimum-size set covers of I, i.e., all smallest-possible size subsets S' of S such that the union of all sets in S' is equal to I.

Write and document a Python program that uses the recursive DFS-I (no dynamic pruning) algorithm given in course lecture # 4 to print all minimum-size set covers for a given MSC instance in which the elements i1, i2, ..., ib are the integers 1, 2, ..., n. You have been given Python files myCSTMSCClasses.py and CSTMSC.py and you need to fill in the function definitions in file myCSTMSCFunctions.template according to appropriately modified versions of the specified algorithm given in Lectures #4 to create a file myCSTMSCFunctions.py such that CSTMSC.py (when run relative to given problem-description files iset1.txt, iset2.txt, iset3.txt, iset4.txt, iset5.txt, iset6.txt, iset7.txt, and iset8.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 CSTMSC.py and myCSTMSCClasses.py. When modifying file myCSTMSCFunctions.template to create myCSTMSCFunctions.py, you cannot:

• modify the given import statements;
• 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 myCSTMSCClasses.py); or
• access any provided class attributes directly (use provided attribute access functions in file myCSTMSCClasses.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 myCSTMSCFunctions.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 #1               ##
##   Script File Name: myCSTMSCFunctions.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 #1 posted.

Created: November 29, 2024
Last Modified: January 15, 2025