Theory of Algorithm Analysis 1. Greedy algorithms: The principle of a greedy algorithm is to find a near best solution for local conditions. For instance,

Theory of Algorithm Analysis 1.

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.

(Graduate) (1) Design the cashier’s algorithm for any coin-change systems. You can assume the single coin values up to 10 different coins (m<=10). You can assume that the changes are in between 1-99 cents (1<=n<=99). (2) What is the time complexity with respect to "m" and "n?" (Undergraduate) (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. Using dynamic programming to calculate comb(n,m)=comb(n-1,m-1)+comb(n-1,m) where comb(n,m)=1 when n<=m, n=0, or m=0 .