COS 226 Programming Assignment Checklist: Bin Packing

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. We will compile your programs with the following commands:

gcc worstfit.c pq.c item.c
gcc bestfit.c st.c item.c

Even if you don't use priority queues or symbol tables, use these file names or risk angering your grader!

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

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 generate.c to generate random test instances. It takes 4 command line inputs N, l, u, and s and generate N pseudorandom integers between l and u using the seed s. The fourth command line input s is optional: if it is not supplied the seed for rand() is set arbitrarily via the system clock; otherwise s is used as the seed.

Reference solutions. For reference, we provide our executable code for the two heuristics on Windows, Solaris, and OS X.

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.c. 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, the number of disks used by worst-fit, worst-fit decreasing, best-fit, and best-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 and best-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, and a BST-based symbol table ADT.

Write a warmup PQ client that uses the given item and pq data types.

Use the KEYscan() and ITEMinit() functions to read values from an input file and create Items.
Insert each Item into a priority queue. (Don't forget to initialize it!)
Print the sum total of the input values.
If there are less than 100 Items, print them in descending order using ITEMshow() along with calls to to priority queue interface. (Hint: review Sedgewick section 9.4)

Don't worry about storing the individual sound file sizes in the disks for now. Instead, implement the worstfit heuristic and just keep track of the remaining space in each disk.

Write a warmup ST client that uses the given item and st data types.

Use the KEYscan() and ITEMinit() functions to read values from an input file and create Items.
Insert each Item into a symbol table. (Don't forget to initialize it!)
Print the sum total of the input values.
If there are less than 100 Items, print them in descending order. To do this, you should add a function to st.h and st.c. Use your ITEMshow() function in the implementation. (Hint: review Sedgewick section 12.5)

Before writing bestfit, think carefully about the operations that you will need to support. Make sure that you understand why a binary search tree is so useful (as opposed to a heap or hash table).

Now, modify item.h and item.c so that each Item stores the individual multiple sound file sizes. (If you're out of time or energy, you can skip this step and take a 2 point deduction.) Re-write ITEMinit(), ITEMshow(), ITEMkey(), and ITEMnull() functions to correspond to your new Item data type definition. If you exercises sound design, you shouldn't need to make changes except in item.c. But, this will take some careful thought. You'll lose one point 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. For full credit use a linked list or dynamic array.

Test your programs on lots of input data.

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.

cos226 Home Page
rs@cs.princeton.edu

Last modified: February 6, 2001