1) We would like to solve the Change-making problem using Dynamic Programming Approach. Change-making problem is...

 

Transcribed Image Text:

1) We would like to solve the Change-making problem using Dynamic Programming Approach. Change-making problem is to give change for amount n using the minimum number of coins of denominations d 0, F(0) = 0 a) If amount n = 9 and m = 3 coin denominations are 1, 2, and 5. Find F(9) by showing on a one-row table and by explaining your steps showing how you found F(1), F(2), F(3), F(9). (10 points) b) Write the pseudo code for the dynamic programming algorithm. (10 points) c) What is the time and space complexity of the algorithm? (10 points) 1) We would like to solve the Change-making problem using Dynamic Programming Approach. Change-making problem is to give change for amount n using the minimum number of coins of denominations d 0, F(0) = 0 a) If amount n = 9 and m = 3 coin denominations are 1, 2, and 5. Find F(9) by showing on a one-row table and by explaining your steps showing how you found F(1), F(2), F(3), F(9). (10 points) b) Write the pseudo code for the dynamic programming algorithm. (10 points) c) What is the time and space complexity of the algorithm? (10 points)