CODEWITHSUNDEEP
algorithmtheorygreedy
Tumelo Dakarai
Tumelo Dakarai

Reputation: 33

Prove or give a counter example for this greedy algorithm

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.

Upvotes: 3

Views: 1902

Answers (1)

Patrick87
Patrick87

Reputation: 28292

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.

Upvotes: 3

Related Questions