A brief lecture discussing a dynamic programming problem, and the
conditions under which one can and cannot use a greedy
algorithm.
The context of this presentation assumes that students have already
been introduced to both dynamic programming and greedy algorithms,
but are puzzled as to when one or the other
technique applies (something I have found is a common problem).
And the idea that opportunity cost is the differentiator here needs
to be refined a bit: I only arrived at this today while preparing
this lecture. The refinement is needed because even in the activity
selection problem, there is some opportunity cost: you still
forego some activities in taking the greedy choice. But the
opportunity cost does not "spillover" into other choices. I have
begun work on trying to formalize this notion, and will produce a
paper stating this relationship more precisely.