2. Read the Coin Changing Problem in the handout on Dynamic Programming. Its solution is presented below for reference. Recall this algorithm assumes that an unlimited supply of coins in each denomination d = (di, d2, ..., dn) are available. tvoros oea CoinChange(d, N) 1. n = length[d] 2. for i = 1 ton 3. C[i,0] = 0 4. for i = 1 ton for j = 1 to N if i = 1 and j 1, and 1 sisn, i.e. d = (1, b, b2, ..., bn-1). Does the greedy strategy always produce an optimal solution in this case? Either prove that it does, or give a counter-example. c. Let di = 1 and 2d; s di+1 for 1sisn - 1. Does the greedy strategy always produce an optimal solution in this case? Either prove that it does, or give a counter- example. 2. Read the Coin Changing Problem in the handout on Dynamic Programming. Its solution is presented below for reference. Recall this algorithm assumes that an unlimited supply of coins in each denomination d = (di, d2, ..., dn) are available. tvoros oea CoinChange(d, N) 1. n = length[d] 2. for i = 1 ton 3. C[i,0] = 0 4. for i = 1 ton for j = 1 to N if i = 1 and j 1, and 1 sisn, i.e. d = (1, b, b2, ..., bn-1). Does the greedy strategy always produce an optimal solution in this case? Either prove that it does, or give a counter-example. c. Let di = 1 and 2d; s di+1 for 1sisn - 1. Does the greedy strategy always produce an optimal solution in this case? Either prove that it does, or give a counter- example