1. 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 < P
(a) We want to maximize the number of programs held on the disk. Prove or give a counter-example: we can
use a greedy algorithm that selects programs in order of increasing si
(b) We want to use as much of the capacity of the disk as possible. Prove or give a counter-example: we can
use a greedy algorithm that selects programs in order of decreasing si
2. The English coinage before decimalization included half-crowns (30 pence), florins (24 pence), shillings (12
pence), sixpences (6 pence), threepences (3 pence), and pennies ( “1 pence”). Assume that an unlimited supply
of each denomination is available. Prove or give a counter-example: with these denominations, the greedy
change-making algorithm always produces an optimal solution.
3. Suppose that we have coins of denominations 1, p, p2
, . . . , pn where p, n ∈ N, p > 1, n ≥ 0. Assume that an
unlimited supply of each denomination is available. Prove or give a counter-example: with these denominations,
the greedy change-making algorithm always produces an optimal solution.
4. Explain in detail how the selection sort algorithm can be interpreted as a greedy algorithm, using the framework
described in lectures.
5. Recall the greedy algorithm for finding a decomposition as a sum of Egyptian fractions. Prove that this algorithm
always terminates (we already know it does not always find an optimal solution, either with respect to number
of summands or size of denominators).
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
In this situation the Greedy approach will fail to provide the optimal solution for all cases. For instance, we can assume we must give change to 50 pence by using the fewest number of coins.
The Greedy approach will select the following solution as being optimal: 30 + 12+ 6+1+1 =50 by using 5 coins...