In my grad algorithms class, I taught matroids. This was last Thursday and came on the heels of a class and problem solving session on greedy algorithms. The class, I think, went well. I went slowly (Socratically), building up the definition of a matroid using the graphic matroid as an example, motivated by Kruskal’s algorithm for maximum spanning tree. I pointed the class to Jeff Erickson’s notes on the topic, but used the 4 Bill’s treatment of matroids in preparing the lecture. The problem solving session for this topic (yesterday), on the other hand was … well, the questions were too difficult. Yes, I’ve made this mistake before. But this time 4 of the 6 questions ended up being too difficult (for the time given). Oh well.
I think I will teach matroids again in this class. In teaching greedy algorithms, I had many questions along the lines of “when will greedy work?” and I think seeing an abstraction of a whole class of objects for which greedy will work (although not, of course, painting the whole picture) satisfied those questions. It’s also a level of abstraction that hasn’t been included in this class before. A healthy dose of it, I think.
Next up, dynamic programming. Maybe I’ll include Courcelle’s Theorem. (No, I won’t.)