1. Let p1; p2; :::pn be n programs to be stored on a disk. Program pi requires si kilobytes of storage, and the capacity of the disk is D, where s1 + s2 + : : : + sn > D.
(a) Give an ecient algorithm to determine which programs to store on the disk so that the total number of programs on the disk is maximized. If you give a greedy algorithm, be sure to prove that your algorithm is correct by proving both greedy choice and optimal program substructure. What is the running time of your algorithm, in terms of n?
(b) Give an ecient algorithm to determine which programs to store on the disk so that as much of the disk as possible is utilized. If you give a greedy algorithm, be sure to prove that your algorithm is correct by proving both greedy choice and optimal program substructure. What is the running time.