CS 3345.004. Data structures and algorithm analysis
Fall 2018
Assignment 9
Wed, Oct 24, 2018

Due: 8:30 AM, Wed, Oct 31 (in class or on elearning).

This is not a programming assignment.  Write code or pseudocode.


1. In the bin packing problem, objects of different volumes must be packed
   into a finite number of bins or containers, each of capacity C, in a way
   that minimizes the number of bins used. 

   A well-known heuristic for this problem, known as "Worst fit" proceeds as follows.
   Consider the items in the order they are given.
   Put each item into the emptiest bin among those with something in them. 
   Start a new bin if the item does not fit into any bin that has already been started.
   For example, if the sizes are: {3,4,2,3} and the capacity of the bin is C=6,
   then the worst fit algorithm proceeds as follows:

   Item 1: 3 is placed in bin 1:  {3}.
   Item 2: 4 does not fit in bin 1.  A new bin is started for it:  {3}{4}.
   Item 3: 2 is placed in bin 1 because it has most available capacity:  {3,2}{4}.
   Item 4: 3 does not fit in bins 1 and 2. A new bin is started for it:  {3,2}{4}{3}.
   The algorithm returns 3, because it uses 3 bins.

   Write the above algorithm using priority queues and analyze its running time.
	int worstFit(int[] size, int C)  // C is capacity of each bin. Return number of bins used.


Optional problem for extra credit:

2. The "Best fit" heuristic for bin packing works as follows.  Items are considered in
   the given order.  If an item fits in none of the existing containers, a new bin is
   started for it.  Otherwise, it is packed into the container whose available capacity
   is the best fit.  In other words, we choose that container whose available capacity
   is as close to the item's size as possible, from among those containers in which the
   item fits.  In the example from Q1, Best fit works as follows.

   Item 1: 3 is placed in bin 1:  {3}.
   Item 2: 4 does not fit in bin 1.  A new bin is started for it:  {3}{4}.
   Item 3: 2 is placed in bin 2 because its available capacity is closest to 2 but not smaller than 2:  {3}{4,2}.
   Item 4: 3 is placed in bin 1, whose available capacity is closest to 3:  {3,3}{4,2}.
   The algorithm returns 2.

   Choose data structures to implement this algorithm to give the best running time
   and write the algorithm.  Analyze its running time.
	int bestFit(int[] size, int C)

3. In the "First fit" heuristic, items are again considered in the given order and 
   an item is placed in the smallest numbered bin in which it fits.  In the same example,

   Item 1: 3 is placed in bin 1:  {3}.
   Item 2: 4 does not fit in bin 1.  A new bin is started for it:  {3}{4}.
   Item 3: 2 is placed in bin 1, the first bin in which it fits:  {3,2}{4}.
   Item 4: 3 does not fit in bins 1 and 2. A new bin is started for it:  {3,2}{4}{3}.
   The algorithm returns 3.

   Choose data structures to implement this algorithm to give the best running time 
   and write the algorithm.  Analyze its running time.
        int firstFit(int[] size, int C)