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 program in one of the Java, C, or Python programming languages that uses a recursive backtracking algorithm to print all minimum-size set covers for a given item-set I and item-subset set S. This algorithm will consider the set of candidate solutions consisting of all possible subsets of S. This algorithm should incorporate dynamic pruning based on potential optimality, i.e., does the union of all item-subsets in the partial candidate solution plus the union of all remaining item-subsets that could be added to the candidate solution equal I AND is the number of item-subsets in the partial candidates solution less than or equal to the number of item-subsets in the best solution found so far? 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).

Questions 2 -- 6

The text of these questions is available in PDF format.

Assignment Submission

Please submit your program files for Q1 and answer text PDF file for Q2--6 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 2023), 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 17, 3:40pm
  Assignment #1 posted.

Created: November 18, 2022
Last Modified: February 14, 2023