The Algorithm Design Manual Second Edition

s

i

use as much of the capacity of the disk as possible? Prove or give a counter-

example.

8-6. [5] Coins in the United States are minted with denominations of 1, 5, 10, 25, and

50 cents. Now consider a country whose coins are minted with denominations of

{d

1

, . . . , d

k

} units. We seek an algorithm to make change of n units using the

minimum number of coins for this country.

(a) The greedy algorithm repeatedly selects the biggest coin no bigger than the

amount to be changed and repeats until it is zero. Show that the greedy algorithm

does not always use the minimum number of coins in a country whose denominations

are

{1, 6, 10}.

(b) Give an efficient algorithm that correctly determines the minimum number of

coins needed to make change of n units using denominations

{d

1

, . . . , d

k

}. Analyze

its running time.

8-7. [5] In the United States, coins are minted with denominations of 1, 5, 10, 25,

and 50 cents. Now consider a country whose coins are minted with denominations

of

{d

1

, . . . , d

k

} units. We want to count how many distinct ways C(n) there are

to make change of n units. For example, in a country whose denominations are

{1, 6, 10}, C(5) = 1, C(6) to C(9) = 2, C(10) = 3, and C(12) = 4.

(a) How many ways are there to make change of 20 units from

{1, 6, 10}?

---

312

8 .

D Y N A M I C P R O G R A M M I N G

(b) Give an efficient algorithm to compute C(n), and analyze its complexity.

(Hint: think in terms of computing C(n, d), the number of ways to make

change of n units with highest denomination d. Be careful to avoid overcount-

ing.)

8-8. [6] In the single-processor scheduling problem, we are given a set of n jobs J . Each

job i has a processing time t

i

, and a deadline d

i

. A feasible schedule is a permutation

of the jobs such that when the jobs are performed in that order, every job is finished

before its deadline. The greedy algorithm for single-processor scheduling selects the

job with the earliest deadline first.

Show that if a feasible schedule exists, then the schedule produced by this greedy

algorithm is feasible.

Number Problems

8-9. [6] The knapsack problem is as follows: given a set of integers S =

{s

1

, s

2

, . . . , s

n

},

and a given target number T , find a subset of S that adds up exactly to T . For

example, within S =

{1, 2, 5, 9, 10} there is a subset that adds up to T = 22 but

not T = 23.

Give a correct programming algorithm for knapsack that runs in O(nT ) time.

8-10. [6] The integer partition takes a set of positive integers S = s

1

, . . . , s

n

and asks if

there is a subset I

∈ S such that