 # 5 Problems Involving Greedy Algorithms

## Transcribed Text

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 i si . (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).

## Solution Preview

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...
\$50.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.