• Site Map

• Lectures

• Homework

• Tests/Exam

• Main Webpage

Homework Exercise 1

Due: by 6pm on Tue 16 Sep
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

1. Consider the problem of making change for some amount of money n, given denominations 1 = d₁ < d₂ < ... < d_k (for example, Canadian coins come in denominations d₁ = 1, d₂ = 5, d₃ = 10, d₄ = 25, d₅ = 100, d₆ = 200). Say that we want the output to be a sequence of coins S = c₁, c₂, ..., c_m (where for each i, c_i = d_j for some j) such that we use as few coins as possible (i.e., n = c₁ + c₂ + ... + c_m and m is minimal).

   For example, 10,1,25,1,1,25 is a solution for n = 63, given the Canadian denominations above, because 63 = 10+1+25+1+1+25 and any other way of making change for 63 cents uses at least six coins.

   1. Give a greedy algorithm that makes change for any amount n >= 0 using as few coins as possible, for the Canadian denominations given above.
      Analyze the runtime of your algorithm, and justify briefly that your algorithm always returns an optimal answer — no need for a formal proof, but make sure that your argument captures the reason why your algorithm works for this problem, in particular, that your argument does NOT apply to similar problems where your algorithm would fail.

      Hint: Treat the solution as a sequence of individual coins (with repetitions allowed, obviously).

   2. Suppose that we run out of nickels, i.e., the denominations become d₁ = 1, d₂ = 10, d₃ = 25, d₄ = 100, d₅ = 200.
      Does your algorithm still work correctly? Justify.

      Hint: Make sure that your justifications for parts (a) and (b) do not contradict each other...