COS 226 Programming Assignment Checklist: Bin Packing

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 Compile button on the Web submission system. Is this OK? No. You will lose a substantial number of points if you don't follow the instructions.

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.

Am I required to format the list of file sizes exactly as in the reference solution? No, this is not a requirement. Java 1.5 will contain a method System.out.printf that will be similar to the C version. Until then, 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 and SymbolTable.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, and Testing

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.

readme.txt

You may use the following readme file template. Besides providing details about your implementation which are not clear from the comments within your source code, your readme.txt file should also contain:

• For the analysis, generate some input files with random file sizes between 0 and 200000, and between 100000 and 700000 using Generator.java. Create two tables (one for each class of inputs) as follows: for each value of N = 100, 1000, 10000, 100000, 1000000, print the total of the file sizes (in GB), the number of disks used by worst-fit and worst-fit decreasing (even better if you report the average over several random trials for each value of N). Print the running time in seconds for worst-fit.

• Discuss the relative effectiveness of the heuristics. The number of disks is the most important factor, but you should also comment the running time.

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. It contains a number of sample input files, a problem instance generator, a priority queue ADT, a template readme.txt file.

• 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 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 two 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.