Exercise 7.7. The bin packing problem is as follows: we are given a set of n objects, where the size si of the i-th object satisfies 0 < si < 1, and an unlimited supply of unit-sized bins. We wish to pack all the objects into the minimum number of bins. Each bin can hold any subset of the objects as long as the total size of the objects does not exceed 1.

(a) Consider the following greedy algorithm for assigning objects to bins: Assume you have already placed objects 1, 2, . . . , k 1 into bins 1, 2, ..., i. To place object k, consider the bins with increasing indices and place object k into the first bin that can accommodate it. If none of the i bins can, place object k into a new bin. Show that this greedy algorithm does not always return the optimal solution to the bin packing problem. Note that you do not have to give an implementation of the algorithm.

(b) Consider another greedy algorithm for assigning objects to bins: Assume you have already placed objects 1, 2, . . . , k 1. Place object k in a used bin that has the maximum amount of available space. If no such bin exists, put the object in an unused (new) bin. 1. Give an example showing that the above greedy algorithm does not always generate the optimal solution (i.e., it may not necessarily pack all the objects in the smallest number of bins). 2. Describe how to efficiently implement the above algorithm using a heap data structure. Analyze the running time of your algorithm For your analysis, you can assume an implementation of the heap operations with the appropriate run time.)