show that any online bin packing algorithm can be forced to use at least the optimal number of binsby considering the following sequence of itemsn items of size items of size items of size give simple analysis to show the performance bound for first fit decreasing bin packing when the smallest item size is larger than the smallest item size is larger than the smallest item size is smaller than explain how to implement first fit and best fit in ( log ntime show the operation of all the bin packing strategies discussed in section on the input write program that compares the performance (both in time and number of bins usedof the various bin packing heuristics prove theorem prove theorem points are placed in unit square show that the distance between the closest pair is ( - / argue thatfor the closest-points algorithmthe average number of points in the strip is on(hintuse the result of the previous exercise write program to implement the closest-pair algorithm what is the asymptotic running time of quickselect using median-of-median-ofthree partitioning strategy show that quickselect with median-of-median-of-seven partitioning is linear why is median-of-median-of-seven partitioning not used in the proof implement the quickselect algorithm in quickselect using medianof-median-of-five partitioningand the sampling algorithm at the end of section compare the running times much of the information used to compute the median-of-median-of-five is thrown away show how the number of comparisons can be reduced by more careful use of the information complete the analysis of the sampling algorithm described at the end of section and explain how the values of and are chosen show how the recursive multiplication algorithm computes xywhere and include all recursive computations show how to multiply two complex numbers bi and di using only three multiplications show that xl yr xr yl (xl xr )(yl yr xl yl xr yr