Question 3.91

61. We have described two algorithms for bin packing called worst fit and best fit (see page 97 and Exercise 60). The words best and worst have connotations in English. However, the performance of algorithms depends on their merits as algorithms, not on the names we give them.

  1. On the basis of experiments you perform with the best-fit and worst-fit algorithms, which one do you think is the “better” of the two?
  2. Can you construct an example where worst fit uses fewer bins than best fit?

61.

(a) Answers will vary.

(b) It is possible.