Consider the Change$-$Making problem. Given a target change of K$=8$ and a set of n$=4$ coin denominations with the following values val $=[1,2,4,5],$ we want to compute the minimum number of coins needed to make the exact amount of change.

Q$1$: Consider a greedy approach to solving the problem. The approach is to add coins in decreasing order of value. How many coins would this greedy approach produce for the K$=8$ change and the four coin denominations described above?

Q$2$: The pseudo$-$code below is a dynamic programming solution to the problem.

int$[]$ CM $=$ new int$[$K$+1]//$table for subproblem solutions

CM$[0]=0//0$ coins for $0$ change

for $($int c $=1$; c $<=$ K; c$++)\{//$solve subproblems bottom up

int min $=$ Integer.MAX$\_$VALUE;

for $($i $=0$; i $<$ n; i$++)\{//$for all coin denominations

if $($val$[$i$]<=$ c && $1+$ CM$[$c $-$ val$[$i$]]<$ min$)\{$

min $=1+$ CM$[$c $-$ val$[$i$]]$;

$\}$

$\}$

CM$[$c$]=$ min;

$\}$

Q$3\mathrm{.}2$: What is the value of CM$[2]?$

Q$3\mathrm{.}3$: What is the value of CM$[6]?$

Q$3\mathrm{.}4$: What is the value of CM$[7]?$

Q$3\mathrm{.}4$: What is the minimum number of coins to make the exact change amount of K$=8?$