1. Suppose we extend binomial queues to allow at most two trees of the same height per structure. Can we obtain O(1) worst-case time for insertion while retaining O(log N) for the other operations?
2. Suppose you have a number of boxes, each of which can hold total weight C and items i1, i2, i3, ... ,iN, which weigh w1, w2, w3, ... , wN, respectively. The object is to pack all the items without placing more weight in any box than its capacity and using as few boxes as possible. For instance, if C = 5, and the items have weights 2, 2, 3, 3, then we can solve the problem with two boxes.
In general, this problem is very hard, and no ef?cient solution is known. Write programs to implement ef?ciently the following approximation strategies:
a. Place the weight in the ?rst box for which it ?ts (creating a new box if there is no box with enough room). (This strategy and all that follow would give three boxes, which is suboptimal.)
b. Place the weight in the box with the most room for it.
c. Place the weight in the most ?lled box that can accept it without over?owing.
d. Are any of these strategies enhanced by presorting the items by weight?