C1. Purpose: Apply various algorithm design strategies to solve a problem, practice formulating and analyzing algorithms,...

Transcribed Image Text:

C1. Purpose: Apply various algorithm design strategies to solve a problem, practice formulating and analyzing algorithms, implement an algorithm. In the US, coins are minted with denominations of 50, 25, 10, 5, and 1 cent. An algorithm for making change using the smallest possible number of coins repeatedly returns the biggest coin smaller than the amount to be changed until it is zero. For example, 17 cents will result in the series 10 cents, 5 cents, 1 cent, and 1 cent. a) Give a recursive algorithm that generates a similar series of coins for changing n cents. Don't use dynamic programming for this problem. b) Write an 0(1) (non-recursive!) algorithm to compute the number of returned coins. c) Show that the above greedy algorithm does not always give the minimum number of coins in a country whose denominations are 1, 6, and 10 cents. d) Given a set of arbitrary denominations C=(C1,..,Ca), describe an algorithm that C1. Purpose: Apply various algorithm design strategies to solve a problem, practice formulating and analyzing algorithms, implement an algorithm. In the US, coins are minted with denominations of 50, 25, 10, 5, and 1 cent. An algorithm for making change using the smallest possible number of coins repeatedly returns the biggest coin smaller than the amount to be changed until it is zero. For example, 17 cents will result in the series 10 cents, 5 cents, 1 cent, and 1 cent. a) Give a recursive algorithm that generates a similar series of coins for changing n cents. Don't use dynamic programming for this problem. b) Write an 0(1) (non-recursive!) algorithm to compute the number of returned coins. c) Show that the above greedy algorithm does not always give the minimum number of coins in a country whose denominations are 1, 6, and 10 cents. d) Given a set of arbitrary denominations C=(C1,..,Ca), describe an algorithm that