COS 226 Programming Assignment #3

Checklist

Here are the main goals of the assignment.

• Use a priority queue in an interesting domain.
• Create and use a linked list.
• Create a dynamically resizable array.
• Use a heuristic for an NP-hard combinatorial optimization problem.

My program doesn't compile when I hit the Run Script button on the whiteboard submission system.  Is this OK?  No. You will lose a substantial number of points if your code does not compile.

Do I need to use a binary heap?  No, that's just a suggestion, but probably a good one.  However, you should be able to handle the large instances (a million weights).

Can I use the Java library LinkedList or ArrayList?  No, you should not use any library functions on this assignment, except that you can use Java's system sort for IntegerSorter.java.

Am I required to format the list of file sizes exactly as in the reference solution? No, this is not a requirement, but if you wish, you can use the Java library DecimalFormat.

Do I need to implement a full blown version of a linked list data type?  No. We recommend defining an inner class for your linked data structure inside Disk.java, similar to the way we implemented Queue.java in COS 126.

Why doesn't Disk d = pq.delMax(); work?  The method delMax returns an Object. You need an explicit cast to convert from the more general type Object to the more specific type Disk.  The cast is not needed (or recommended) with insert since you are converting from a more specific type to a more general type.

Input, Output, Testing, Submitting

Input.   Your program should read in a sequence of integers between 0 and 1000000 separated by whitespace from standard input. Here are some sample input files. You may also use Generator.java to generate random test instances. It takes 3 command line inputs N, L, and U, and generates N pseudorandom integers between L and U.

Reference solutions.   For reference, we provide our executable code for the two heuristics on Windows, Solaris, and OS X. Choose the version of worstfit226 for your operating system and execute with worstfit226 < input.txt. Note that these programs were written in C, so you may see slightly different behavior, e.g., the formatting of the numbers. Also, the priority queue is not "stable", so although the remaining capacities of all the disk should match, you may get different file sizes on some disks.

Program report.  You also need to submit a brief written report on what you did for this assignment that answers these questions.  Besides providing details about your implementation which are not clear from the comments within your source code, your program report should also contain an empirical comparison of the heuristics and a discussion of their effectiveness.  This report should be submitted electronically using whiteboard with your source code files.  You can submit either plain text or pdf.  The submitted program report file should be called either report.txt or report.pdf.  See the assignments page for more details on how to submit.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

• Download the directory bins to your system (also available on arizona in ~cos226/ftp/spring/bins).  It contains a number of sample input files, a problem instance generator, a priority queue ADT and reference solutions.

• Implement IntegerSorter.java. Read in the data from standard input, put it in an integer array, and use the system sort.  The main challenge is that you don't know how many integers you'll be reading in.  Use a repeated-doubling strategy to dynamically resize the array as needed.

• Create a data type Disk.java to represent a disk.  For now, give it a data member to store the amount of space left (and possibly a unique id for use in debugging).  Make Disk implement the Comparable interface so that you will be able to insert disks onto a priority queue.  Also, include a toString method for debugging and to produce the required output.

• Write the client program WorstFit.java to implement the worst-fit algorithm.  But only keep track of the remaining space in each disk, instead of remembering which sound file sizes go with which disks. You may wish to add some (very minor) functionality to your priority queue interface.

• Modify Disk.java so that each Disk stores a list of the sound file sizes that it stores.  Include a method to add an (integer) sound file size to the disk.  For full credit use a linked list or dynamic array.  You'll lose points if you use a fixed size array since you'll either waste memory or prevent a bunch of small file sizes from being placed in one disk.

• Update WorstFit.java so that it adds sound file sizes to the appropriate disks.

• Test your programs on lots of input data.

Researchers have proved some amazing things about bin packing heuristics.  For example, if the optimal packing uses B bins then the best-fit decreasing algorithm is guaranteed to use no more than 11B/9 + 1 bins (within 22% of best possible). The original proof of this result (for the first-fit decreasing heuristic) required over 70 pages of analysis!  The file worstcase30.txt gives a worst-case instance where the best-fit decreasing algorithm uses 11 bins even though the weights fit snugly into 9 bins.