analysis of algorithms 4

Greedy algorithms: The principle of a greedy algorithm is to find a near best solution for local conditions. For instance, a cashier gives coin changes to a customer, the best way is to give the smallest number of coins to the customer. However, it is usually hard to make such an arrangement. The cashier usually gives the largest valued coins first until could not give more, then select the second largest valued coins to the customer. And so on so forth.

For instance, for 48 cents, the cashier usually give one “25c”, two “10c”, and three”1c” coins. This algorithm is called the cashier’s algorithm that is a greedy algorithm. According to the previous research, the cashier’s algorithm is already the optimum for the US coin change system. Meaning that the cashier’s algorithm will give the best solution for US coin changes.

If a coin system is randomly assigned, for instance, there is no “5c”–nickel. The cashier’s algorithm may not reach the optimum in some cases.

(1) Write a C++ or Java program to implement the cashier’s algorithm. (You can just use the US coin changes as the example.)

(2) Write an essay about the greedy algorithm (1-2 pages).