There is a series of n coins with values C = [c1, c2, ..., cn]. Values...

Transcribed Image Text:

There is a series of n coins with values C = [c1, c2, ..., cn]. Values are positive integers and duplications are allowed. For example, a possible set of coins is: C7 = [5, 20, 2, 20, 1, 10, 50]. Your goal is to raise the maximum amount of money by limiting that you will not get two coins side by side in the starting lineup. For example, if you get coin 10 from C7, then you can not get 1 or 50 coins. a) Write the recurrence equation to find maximum amount M (n) you can get from a series of n coins. b) Write pseudocode to find the maximum amount M (n) using an auxiliary table. Note that this method should not be recursive. c) What is the running time and the space of the above algorithm? d) Describe a way to find out which coins are needed to get the maximum amount. Note: You can use a second table or extract the solution from the first table you used in part (b). There is a series of n coins with values C = [c1, c2, ..., cn]. Values are positive integers and duplications are allowed. For example, a possible set of coins is: C7 = [5, 20, 2, 20, 1, 10, 50]. Your goal is to raise the maximum amount of money by limiting that you will not get two coins side by side in the starting lineup. For example, if you get coin 10 from C7, then you can not get 1 or 50 coins. a) Write the recurrence equation to find maximum amount M (n) you can get from a series of n coins. b) Write pseudocode to find the maximum amount M (n) using an auxiliary table. Note that this method should not be recursive. c) What is the running time and the space of the above algorithm? d) Describe a way to find out which coins are needed to get the maximum amount. Note: You can use a second table or extract the solution from the first table you used in part (b).