Topic: Dynamic Programming / Coin Changing Problem

Textbook: Algorithm Design, kleinberg and tardos

Do part (A) only (and maybe parts (C) and (E) if you can...or the whole thing...thanks!)

(Coin Changing) Greedily finding the smallest number of coins to make change is opti- mal if we are given quarters, dimes, nickels, and pennies. However, without nickles we can not use a greedy approach to find the fewest number of coins to make change (pick, for example, 30 cents) (a) Let OPT(n) be the fewest number of coins required to make change for n cents if we are only given quarters, dimes, and pennies. Describe a recurrence relation for OPT(n) (b) Use your answer from part (a) and write a program in the programming lan- guage of your choice to compute OPT(n). Include your program in your pdf using the verbatim environment (c) Let OPT-COINS(n) be a 3-tuple of integers representing a set coins that may be used to obtain the minimum number of quarters, dimes, and pennies That is, if OPT-COINS (n) (p, d, q), then we use p pennies, d dimes, and q quarters, and furthermore p+4+9 = OPT(n). Describe a recurrence relation for OPT-COINS(n) (d) Use your answer from part (c) and write a program in the programming lan- guage of your choice to compute OPT-COINS(n). Include your program in your pdf using the verbatim environment (e) Prove that the coin changing problem has optimal substructure. That is, if (p, d, q) is an optimal solution for n > 0, then at least one of the following statements is true: 1. (p - 1, d, q) is an optimal solution for n -1, 2. (p, d - 1,q) is an optimal solution for n - 10, or 3(p,d, q-1) is an optimal solution for n-25 Note that at least one of these statements may be true, or perhaps all of them For example, for n 1 the optimal solution is just a penny, so only the first statement is relevant (it does not make sense to make change for n - 10 or n 25 in this case (Coin Changing) Greedily finding the smallest number of coins to make change is opti- mal if we are given quarters, dimes, nickels, and pennies. However, without nickles we can not use a greedy approach to find the fewest number of coins to make change (pick, for example, 30 cents) (a) Let OPT(n) be the fewest number of coins required to make change for n cents if we are only given quarters, dimes, and pennies. Describe a recurrence relation for OPT(n) (b) Use your answer from part (a) and write a program in the programming lan- guage of your choice to compute OPT(n). Include your program in your pdf using the verbatim environment (c) Let OPT-COINS(n) be a 3-tuple of integers representing a set coins that may be used to obtain the minimum number of quarters, dimes, and pennies That is, if OPT-COINS (n) (p, d, q), then we use p pennies, d dimes, and q quarters, and furthermore p+4+9 = OPT(n). Describe a recurrence relation for OPT-COINS(n) (d) Use your answer from part (c) and write a program in the programming lan- guage of your choice to compute OPT-COINS(n). Include your program in your pdf using the verbatim environment (e) Prove that the coin changing problem has optimal substructure. That is, if (p, d, q) is an optimal solution for n > 0, then at least one of the following statements is true: 1. (p - 1, d, q) is an optimal solution for n -1, 2. (p, d - 1,q) is an optimal solution for n - 10, or 3(p,d, q-1) is an optimal solution for n-25 Note that at least one of these statements may be true, or perhaps all of them For example, for n 1 the optimal solution is just a penny, so only the first statement is relevant (it does not make sense to make change for n - 10 or n 25 in this case