Assignment 4

Question 1

Recall the Minimum Set-Cover (MSC) problem from Assignment #2 -- namely, given a set I of items and a set S of subsets of I, find all subsets S' of S such that the union of all item-subsets in S' is I. Consider the following greedy algorithm for this problem:

          U = I
          Set C to the empty set
          While U is not empty do
              Select item-subset s in S that maximizes the size of
               the intersection of s and U
              U = U - s
              C = C union {s}
          return C

Though this algorithm is not guaranteed to always produce minimum set-covers, it frequently produces set-covers whose size is close to the minimum.

Write and document a Java program that implements the greedy algorithm given above and compares its performance against the CST optimal-solution algorithm for the MSC problem from Assignment #2. Your program will take as command-line input the number of items in I and the number of item-subsets in S, and will use the provided Java file InstanceSC.java to generate instances of the MSC problem. All methods in this class are the same as the methods in this class as given in the answer-code for Assignment #2 except the constructor, which takes int parameters numItems and numSets and returns a randomly-generated instance of MSC with those characteristics, e,g, a numSets X numItems 2-D boolean array set such that item j is in item-subset i if and only if set[i - 1][j - 1] = true. Note that these generated datasets need not have a solution, i.e, there may be no cover-subset of S for I. Your program will generate 50 such datasets, and for each dataset, run the greedy and CST algorithms to obtain solutions. For each of the 50 datasets that has a solution, compute the ratio C*/C, where C (C*) is the cost (number of item-subsets in) the CST (greedy) solution, and compute and display the minimum, average, and maximum ratio-value over all of the 50 datasets with solutions. For each of the 50 datasets (regardless of whether or not it has a solution), compute the running times for the greedy and CST algorithms, and compute and display the minimum, average, and maximum running-time (in seconds) over all 50 datasets. You can get a rough estimate of the running-time (in milliseconds) of a piece of code using the Java GregorianCalendar class and the following code-fragment:

          import java.util.GregorianCalendar;
          
                            ...
          
              Gregorian Calendar before, after;
              float	       runTimeSeconds;
          
                            ...
          
              before = new GregorialCalendar();
              ... code of interest ...
              after = new GregorialCalendar();
              runTimeSeconds = (after.getTimeInMillis() - 
                                before.getTimeInMillis()) / 1000.0F;
          
                            ...
          

Examples of several program runs are given in script file out.script. Note that as datasets are generated using the Java Random class constructor in default mode with program execution time as the random-number generator seed, no two runs of this program will produce exactly the same results.

Hints

As you only need to compute the cost of set-covers, you can simplify the greedy algorithm and the CST algorithm from Assignment #2.

Questions 2 -- 4

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 -- 4. 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 #4, Question #1            //
//  Program File Name: SCGrd.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:

• Nov 16, 5:15pm
  Due to possible inconsistencies in Java compiler versions, revised Assignment #4 description to provide class InstanceSC Java code instead of .class file.

• Nov 15, 8:45am
  Assignment #4 due date revised to Friday, November 18.

• Oct 26, 1:55pm
  Assignment #4 posted.

Created: October 26, 2005
Last Modified: November 16, 2005