H. Thoreau once said "In proportion as he simplifies his life, the laws of the universe will appear less complex.." (Walden, Princeton University Press, 1971, p.323-324)
I'd love to see the entire course in the format of that first lecture linked above, i.e you start with a naive implementation and gradually improve it both algorithmically and with language-specific hacks until you get orders of magnitude faster version working on your machine, not on paper.
Add parallel algorithms to the mix. Ask to parallelize serial algorithms that you explain in the lecture. They should at least start thinking about programming for multicore and clusters, they will thank you for that later.