Glencora Borradaile

         Associate Professor & College of Engineering Dean's Professor, School of Electrical Engineering and Computer Science, Oregon State University

October 19, 2011

Teaching Matroids

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.)

Print Friendly, PDF & Email


  1.   Chandra — October 19, 2011 @ 9:12 am    

    I am teaching graduate algorithms this semester and taught matroids. I introduce matroids via vectors and abstract notion of independence systems which is how Whitney defined them. And then show that graphs are also captured. I feel that discussing history and the original motivation is often useful for students to see. I don’t personally like motivating matroids via the greedy algorithm for MST because it is dry and seems some what of an artificial jump and is histortically not accurate.

    •   Glencora — October 20, 2011 @ 7:33 am    

      Do you find it interesting enough to get to the definition of matroids using … definitions?

      My motivation by getting there through example was to have the students see what it is about forests and trees that allows the greedy algorithm to work. Since they are very comfortable with MSTs, they have some interesting ideas for this. But I don’t think students would arrive at the very abstract notion of a matroid without the motivation to characterize a structure that can be found greedily.

  2.   Stefan — October 19, 2011 @ 9:29 am    

    From an algorithmic point of view, matroid intersection is the big star. Furthermore, Seymour’s Decomposition Theorem is of interest for integer programming. I like to think (though I never tried) that one can pretty quickly teach matroids to the point that the statement of the theorem can be understood.

    •   Glencora — October 20, 2011 @ 7:29 am    

      Yes, I agree! If I could have gotten there within 2 lecture hours, I would have done it. Sadly, spending more than one of ten weeks on matroids isn’t an option in this “core” grad class.

  3.   D. Eppstein — October 19, 2011 @ 11:42 am    

    Some exciting news about matroids:

  4.   Chandra — October 19, 2011 @ 12:51 pm    

    The result of Geelen, Gerards and Whittle for binary matroids is not so new in that they have been speaking about it for the last few years.

  5.   Stasys — October 20, 2011 @ 10:36 am    

    Perhaps this short excerpt from 2nd edition of my “Extremal Combinatorics” book could be interesting in matroids class. It deals with the question: when greedy algorithms can *approximate* the problem?

  6.   Stasys — October 20, 2011 @ 10:40 am    

    … sorry, doesn’t seem to work here. The link is:

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

© 2019 Glencora Borradaile   Powered by WordPress MU    Hosted by