COS 226 Programming Assignment Checklist: Bin Packing

(10/3) Note: the bestfit executables have been re-posted. The previous versions had a minor bug. Sorry for the inconvenience.

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 (long) 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 is optional: if it is not supplied the seed is set arbitrarily via the system clock.

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 symbol table ADT.

  • Write a warmupPQ client that uses the given item and pq data types.
    1. Use the SIZEscan and ITEMinit functions to read values from an input file and create Items.
    2. Insert each Item into a Priority Queue. (Don't forget to initialize it!)
    3. Print the sum total of the input values.
    4. If there are less than 100 Items, print them in descending order using ITEMshow and your priority queue. (Hint: review Sedgewick section 9.4)

  • Write a warmupST client that uses the given item and st data types.
    1. Use the SIZEscan and ITEMinit functions to read values from an input file and create Items.
    2. Insert each Item into a Symbol Table. (Don't forget to initialize it!)
    3. Print the sum total of the input values.
    4. 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)

  • Without changing your warmup clients or the pq and st ADTs, modify item.h and item.c so that each Item would be capable of holding multiple sound file sizes. Review the assignment instructions to determine the requirements for your Item type. Re-write the ITEMinit, ITEMshow, ITEMkey, and ITEMnull functions to correspond to your new Item data type definition. Use your same warmup clients to help you debug your code. (Effectively, you are just storing one sound file size per disk, regardless of size.) For both clients, you should get the following results for the input20.txt data: 
    File sizes sum: 6580996 Kb
 9  795935:  204065 
 6  769027:  230973 
17  745726:  254274 
 7  737074:  262926 
16  736515:  263485 
 3  713691:  286309 
 2  688989:  311011 
 4  679586:  320414 
11  675613:  324387 
14  673415:  326585 
10  668188:  331812 
15  659810:  340190 
 8  652440:  347560 
13  652339:  347661 
 1  648457:  351543 
18  616028:  383972 
19  607981:  392019 
 5  603705:  396295 
 0  579287:  420713 
12  515198:  484802

  • Before writing code for the two heuristics, think carefully about the data structures and operations that you will need to support.

  • 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