I just started greedy algorithms and I'm having some issues.

I looked at: https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/04GreedyAlgorithmsI-2x2.pdf

the proof is in slides 5-6. The algorithm is straightforward and the properties are clear, but I don't understand the induction in slide 6:

Theorem. Cashier's algorithm is optimal for U.S. coins: 1, 5, 10, 25, 100. Pf. [by induction on x]

  • Consider optimal way to change ck ≤ x < ck+1 : greedy takes coin k.
  • We claim that any optimal solution must also take coin k.
    • if not, it needs enough coins of type c1, …, ck–1 to add up to x
    • table below indicates no optimal solution can do this
  • Problem reduces to coin-changing x – ck cents, which, by induction, is optimally solved by cashier's algorithm

I know induction as in base case, induction hypothesis, and the induction step, but it seems like it is missing here.

My question:

What is the induction hypothesis and induction step here? Why is this proof valid?


Base case: $k=1$. Suppose that you want to change a value $x$ between $c_1=1$ (inclusive) and $c_2=5$ (not inclusive), i.e. $1\le x<5$. Then, the greedy will take a coin of $k=1$ and will set $x \leftarrow x-1$. That the greedy solves here optimally is more or less trivial.

Induction hypothesis: $k$. The greedy solves optimally for any value of $x$ such that $c_{k-1}\le x<c_k$.

Induction step: $k+1$. Show that the greedy solves optimally for any value of $x$ such that $c_k\le x<c_{k+1}$. Then, they use this table that you mention to show that this problem reduces to solving for $x\leftarrow x-c_k$ for which $0\le x-c_k<c_{k+1}-c_k$, which has been treated in the induction hypothesis.

Note that the table - which is the main part of the proof - can be constructed only for specific values of the coins. It does not hold for any possible choice of coin denominations, as they show in their next slide.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.