• Table of Contents

Algorithmic Paradigms

An algorithm paradigm is a generic model or framework which underlies the design of a class of algorithm. We have already covered some of them, those being:

• Greed: Process the input in some order, myopically making irrevocable decisions.
• Divide-and-conquer: Break up a problem into independent subproblems — solve each subproblem and combine solutions to subproblems to form solution to original problem.
• Dynamic programming: Break up a problem into a series of overlapping subproblems — combine solutions to smaller subproblems to form solution to large subproblem.

We will distinguish the three distinct approach by solving the following problem:

Find the minimum number of coins needed to make change.

• Input: ****An integer $money$ and integers $coin_1$, $\dots$, $coin_d$.
• Output: The minimum number of coins with denominations $coin_1$, $\dots$, $coin_d$ that changes $money$.

To provide a bit of context, suppose we have the following currency denomination:

Figure 5.1 Currency denominations.

And we have to pay the customer $x$ cents, our goal is now to devise a method to pay that amount to the customer while using the fewest number of coins — emphasizing on the “fewest”.

Greedy Way

The greedy approach is the simplest, conceptually. At each iteration, it selects the coin of the largest value, which is not greater than the remaining amount to be paid.

**GreedyChange(*money*)**
*Change* ← empty collection of coins 
while *money* > 0:
	*coin* ← largest denomination that does not exceed *money*
	add *coin* to *Change*
	*money* ← *money* - *coin*
return *Change*

Consider this scenario:

• coins[] = {1,5,10,25,50} where the currency denomination are $1$ cent, $5$ cents, $10$ cents, $25$ cent, and $50$ cents.
• money = 40 where the customer needs $40$ cents.

The algorithm will output Change[] = {25,10,5}, meaning the customer receives $25$ cents, $10$ cents, and $5$ cents. But, is this the optimal solution? Yes.

Figure 5.2a Greedy solution.