4. Recall the coin changing problem from Assignment 4: given coins of denomination di zonks, where 1-d 0. We want to make exact change while minimizing the total weight of the coins used. (a) Suppose the denominations are 1,5, 10,25, 50 with respective weights 1,2, 2,6, 12. Give the optimal solution for n 60. (3 marks) (b) Describe in detail a dynamic programming algorithm to make change for n zonks such that the total weight of coins used is minimized, and give its asymptotic worst-case running time (7 marks) 4. Recall the coin changing problem from Assignment 4: given coins of denomination di zonks, where 1-d 0. We want to make exact change while minimizing the total weight of the coins used. (a) Suppose the denominations are 1,5, 10,25, 50 with respective weights 1,2, 2,6, 12. Give the optimal solution for n 60. (3 marks) (b) Describe in detail a dynamic programming algorithm to make change for n zonks such that the total weight of coins used is minimized, and give its asymptotic worst-case running time (7 marks)