This weekend I prepared a lecture on probabilistic embeddings of metrics by tree metrics (section 8.5 of the Williamson-Shmoys book). I streamlined the presentation a bit to get to a point where I may have the shortest, clearest proof (although still too complicated for a blog post), near-optimal from an NP perspective: the students will hopefully be able to follow easily.

However, it is not satisfactory. Why not? Because the students cannot lead. They have to follow me.

What would I want instead? In the P perspective, I would like the students to discover the algorithm and proof by themselves, perhaps by successive approximations, designing progressively more sophisticated algorithms, where each algorithm encounters an obstacle in the form of some hard input, and the hard input is dealt with by refining the algorithm. When the process is broken down in manageable pieces, the students can do their own design, like someone cooking from basic ingredients.

Unfortunately, in the present case, to teach in that way I am lacking in lecture time, preparation time, and depth of understanding, so the students will have to make do with a ready-made, pre-packaged proof that I will merely microwave during class.

I am confused. Solving problems is NP-Hard so why should it be the case that the students can discover it themselves in all cases even with a reasonable amount of time?

ReplyDeleteThe students have a teacher, who could act as an oracle. This can, and should, make computation easier.

ReplyDeleteThe oracle will not always be there holding the students' hand. I'd rather have them discover the class material without me. My contribution would be to gently pull them away from dead ends, so that they don't waste too much time exploring those paths that lead nowhere.

ReplyDeleteThere is no doubt that a moment of "self discovery" is a sweet spot for joy and comprehension. I believe you strive to provide each student with a personal epiphany on the lecture's subject, which is a excellent and ambitious goal. However, when other factors prevent this (such as lecture time, preparation time, and depth of understanding) students may still benefit from the process of "anagnorisis" which is watching someone else make a critical discovery, as you likely do in a "microwaved lecture". In my opinion, both of these cases are far better than a "spoon fed" lecture, which typically involves presentation of the text verbatim.

ReplyDelete(historical side note: Anagnorisis has been recognized as a critical factor in story telling since Aristotle wrote "Poetics" in 335 BCE)