Assignment 2

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 Java 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. 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 code for solving the 0/1 Knapsack ( Question #1, Assignment #2, CS 3711 (Winter 2002)) and Vertex Cover ( Question #1, Assignment #2, CS 3711 (Winter 2003)) problems). Even though it is written C-language, you may find the organization of the code for solving the 0/1 Knapsack problem of particular use in this assignment.

Questions 2 -- 6

The text of these questions is available in PostScript and PDF format.

Assignment Submission

Please hand in printed copies of all of your Java source code files for Question #1 along with your answers for Questions #2 -- 6. You must also submit the files for Question #1 electronically using the submit-assignment command. Note that each such file must have the following comment block at the top, where the X's are replaced with the appropriate information. For instance, my code for this assignment would begin with the following comment block:

/////////////////////////////////////////////////////////////////
//  CS 3711 (Fall 2005), Assignment #2, Question #1            //
//  Program File Name: SCCST.java                              //
//       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:

• Oct 4, 8:45pm
  Due date revised to Oct 12.

• Sep 23, 3:40pm
  Assignment #2 posted.

Created: September 23, 2005
Last Modified: October 4, 2005