Assignment 1

Question 1

Consider the following problem:
Set Cover
Input: A set I = {i1, i2, ..., in} of items 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 a recursive backtracking algorithm to print all minimum-size set covers for a given item-set I and item-subset set S, where the files specifying I and S are input as command-line arguments. This algorithm will consider the set of candidate solutions consisting of all possible subsets of S. An example item-subset set file iset1.txt is as follows:

5 4
 1: 1 2
 2: 2 3 4
 3: 4 5
 4: 2 3 4

Each such file of m item-subsets of a set of n items consists of n + 1 lines, where the first line contains the integers n and m, respectively, and the remaining lines contain the item-subsets, one per line, where each item-subset is specified by the number of the item-subset and its elements in ascending order. You may assume that all input files are formatted correctly. Examples of several program runs relative to the item-subset set files iset1.txt, iset2.txt, iset3.txt, iset4.txt, iset5.txt, iset6.txt, iset7.txt, and iset8.txt are given in script file out.script.min. It is these results that your program should be able to replicate. To aid understanding how this program should work, you have also been provided with an expanded version of this script file which shows the program's progress through the search tree of candidate solutions.

Hints

You may find it convenient to determine the optimal solution cost and to print optimal solutions in two separate recursive procedures (see sample Java code for solving the Vertex Cover described in Lecture #1).

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 #1, Question #1  ##
##   Script File Name: MSC.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 21, 2023
Last Modified: February 21, 2023