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:

gcc226 worstfit.c pq.c item.c

(see assignment 1 checklist for help on gcc226).

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.

readme.txt

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 and the number of disks used by worst-fit. Print the running time in seconds.

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.

Test your programs on lots of input data.