COS 226 Programming Assignment 3 - Checklist

Checklist 3: Bin Packing

The following is a checklist which provides a summary of the assignment. This is meant only as a supplement; please read the original assignment description.

  • Frequently Asked Questions
  • Requirements
  • Possible Progress Steps
    •

    Frequently Asked Questions:

    Below, when we ask for "verbose" output in your readme, we really do want to know for each bin, the list of all items which were packed into that bin. (Yes, some have realized that you otherwise could get by with just maintaining the sum of the weights in each bin, but in a real application you really do need to know which items to assign to each bin.) If this slows up your code, you may feel free to comment it out when running on the larger inputs.

    The last line of the second paragraph mentions that you are to print out the total of the item weights, and then in parenthesis, says "(best possible number of bins)". Just for the record, the total of the item weights provides a lower bound on the best possible number of bins, but not necessarily the exact best number of bins. (Finding the exact best answer is NP-hard).

    Requirements:
  • Functionality:
  • Your program should generate the random input, output the sum of the weights, calculate and output the number of bins used by "worst fit", and then calculate and output the number of binds used by "worst fit decreasing".
  • Your final priority queue implementation must be heap-based.
  • readme:
    • Besides providing details about your implementation which are not clear from the comments within your source code, your 'readme' file for this program should also contain:
  • Generate verbose output (i.e. the contents of all the bins) for a run of both heuristics when [N=16,u=.2] and for [N=16,u=.7].
  • Give two tables, one for u=.2 and one for u=.7, as follows: For each value of N=100,1000,10000,100000, print the total of the weights, the number of bins used by "worst fit", and the number of bins used by "worst fit decreasing". (even better is if you report the average over several random trials for each value of N).
  • Give a few comments on the relative effectiveness of the two heuristics.
    • Possible Progress Steps: These are purely suggestions for how you might make progress. You do not have to follow these steps.
  • Most important is for you to think a lot about the interface you set up in pq.h ADT. You will have to think a lot about exactly what operations the main program will need to rely on.
  • Once you are happy with your priority queue interface, you can start by implementing a very simple (but ineffecient) method, such as using an ordered array. With this working, you can write the client program and run the heuristics.
  • Of course, with a poor implementation of priority queues, the program will be quite slow for large values of N. Fortunately, if your ADT is designed properly, you can now go and rewrite a more efficient priority queue implementaiton based on heaps.
    • cos226 Class Page
    rs@cs.princeton.edu
    Last modified: February 21, 2001