2.Question is from algorithm analysis & design

Let P, P2 requires si kilobytes of storage, where si D. We look at two different problems (a) We want to use as much of the capacity of the disk as possible i.e. we don't 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 s-1til 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 e. an instance of the proble on which the greedy algorithm produces a solution which is not optimal. To do this, you have to come up with the coun terexample, 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 maximize the number of programs held on the disk. Consider the greedy algorithm that selects the program by increasing size ie. it first selects s1, then s2, .t 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 coun terexample, show what wil be the solution produced by the greedy algorithm, and show that there is actually a better solution on this counterexample