COS 226 Programming Assignment Checklist: Bin Packing

Goals

Here are the main goals of the assignment.

Frequently Asked Questions

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:

Possible Progress Steps

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

Enrichment Section

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.