Let P1, P2, . . . , Pn be n programs to be stored on a disk which can store a total of D kilobytes. Program Pi requires si kilobytes of storage, where s1 < s2 < < sn and Pn i=1 si > D. We look at two different problems :

(a) We want to maximize the number of programs held on the disk. Consider the greedy algorithm that selects the program by increasing size i.e. it first selects s1, then s2, . . . till it runs out of disk space. For example, if D = 20 and the program sizes are 4, 10, 15 the greedy algorithm will first select 4 and then 10 and will thus be able to put two programs on disk - in this example this is the best possible solution.

i. Does the greedy algorithm always produce the best solution for this problem? Give a (YES/NO) answer.

ii. If you have said NO, give a counterexample i.e. an instance of the problem on which the greedy algorithm produces a solution which is not optimal. To do this, you have to come up with the counterexample, show what will be the solution produced by the greedy algorithm, and show that there is actually a better solution on this counterexample.

(b) We want to use as much of the capacity of the disk as possible i.e. we dont care how many programs are held on disk, just that if the total of these sizes is L, then L should be as large as possible. Consider the greedy algorithm that selects the program by decreasing size i.e. it first selects sn, then sn1, . . . till it runs out of disk space. For example, if D = 20 and the program sizes are 4, 10, 15 the greedy algorithm will first select 15, will skip over 10 (because there is not enough space for it) and will then select 4 and will thus be able to use L = 15 + 4 = 19 units of disk space - in this example this is the best possible solution.

i. Does the greedy algorithm always produce the best solution for this problem? Give a (YES/NO) answer.

ii. If you have said NO, give a counterexample i.e. an instance of the problem on which the greedy algorithm produces a solution which is not optimal. To do this, you have to come up with the counterexample, show what will be the solution produced by the greedy algorithm, and show that there is actually a better solution on this counterexample.