Greedy Algorithm

Question

No complicated code: English is the best way to express an algorithm combined with some simple pseudocode when needed.

We want to purchase an item of price M and for that we have an unlimited (!) supply of [log M] types of coins with value 1, 2, 4, · · · , 2ⁱ , · · · , 2 ^{[log M]}. Our goal is to purchase this item using the smallest possible number of coins (it is always possible to buy this item by picking M coins of value 1). Design and analyze a greedy algorithm for this problem with O(log M) runtime.

Examples:

• Given M = 15 (and so [log M] = 4), the correct answer is 4 coins by picking one copy of each of the coins 8, 4, 2, 1. Note that here we cannot pick the coin of value 2^{[log M]} = 2⁴ = 16.

• Given M = 32 (and so [log M] = 5), the correct answer is 1 coin by picking one copy of the coin 32 = 2⁵ = 2^{[log M]}

(a) Algorithm:

(b) Proof of Correctness:

(c) Runtime Analysis:

Answer 1

Inputs N

For loop M downto 1

T =2^loop

Bit = n div t

N = n mod t