Prove or give a counter example for this greedy algorithm

3
votes

I'm having trouble with this homework question. I think the main confusion comes from not identifying a basis for a counter example.

Let P1, . . . , Pn be programs stored on a disk. Program Pi requires Si megabytes of storage, and the capacity of the disk is D megabytes. Where D is less than the sum of megabytes of storage

  • (a) maximize the number of programs held on the disk. Prove or give a counter-example: greedy algorithm that selects programs in order of increasing Si

  • (b) use as much of the capacity of the disk as possible. Prove or give a counter-example: greedy algorithm that selects programs in order of decreasing Si

Edit: Sorry for not clarifying.

For part (a) my initial try was assuming that it does not select programs in order of increasing Si. Choosing Pa, Pb and Pc where Sa<=Sb<=Sc, after this I didn't really understand how to go further and part (b) asks the same question but decreasing Si.

1
algorithmtheorygreedy
Could you be more specific about what you are asking? – Espen
The question is asking to give a greedy algorithm that always finds a maximum subset(maximum subset is one with the maximum number of programs in it). Also to prove the algorithm gives the optimal solution. – Tumelo Dakarai
Have you at least tried to tackle the problem yourself? Can you show us what you've done to try to solve the problem? – TNguyen
sorry,check edit. – Tumelo Dakarai

1 Answers

3
votes

a) Theorem: taking programs in increasing order of disk space required ensures that as many programs run as is possible. Proof: the proof is by contradiction. Suppose there is some other method of choosing programs that allows more to run. Then this method must select a different set of programs in at least one case; that is, it must select at least one program that requires more space than one not selected. However, the method might as well have selected the program requiring less space rather than this other one that differentiates it from the selection made by the greedy algorithm. This contradicts the assumption that this method is better than the greedy method. Therefore, no method is better than the greedy method: it is optimal.

b) Theorem: taking programs in decreasing order of disk space required does not ensure that as much disk space is used as is possible. Proof: the proof is by example. Consider the case of a disk of size 10 and programs requiring disk space 6, 5 and 5. Taking the programs in decreasing order of disk space required allows us to use only 6 of the 10 available storage units, whereas we might have taken two programs requiring 5 units each for 10 total units. Therefore, the greedy approach does not give an optimal result in all cases.