Q: For questions 1a, 2a, 3a, and 4, do we have to give pseudo-code or just an English explanation ?

A: Give pseudo-code, with comments that explain the codes.


Clarification for Q3: You can assume that all given currencies contain the penny, i.e., one
element of the input array C is 1.


An hint for the induction step of Question 3:
======================================================================
Any optimal sequence can contain at most 1 loonie, 3 quarters, 2 dimes
(verify it for 3 & 4 dimes !), 1 nickel and 4 pennies.
(Also note that by the same arguments in the notes, the subsequence
(b_{i+1}, ...) that adds up to > a_{i+1} should not contain pennies.)

  So now we have to go through the cases for a_{i+1}: 200, 100, 25, 10.
They should all be simple using the observation.
======================================================================