{"id":747,"date":"2011-10-19T08:26:24","date_gmt":"2011-10-19T15:26:24","guid":{"rendered":"http:\/\/www.glencora.org\/?p=746"},"modified":"2012-01-28T00:11:05","modified_gmt":"2012-01-28T00:11:05","slug":"teaching-matroids","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/glencora\/2011\/10\/19\/teaching-matroids\/","title":{"rendered":"Teaching Matroids"},"content":{"rendered":"

In my grad algorithms class, I taught matroids. \u00a0This was last Thursday and came on the heels of a class and problem solving session<\/a> on greedy algorithms. \u00a0The class, I think, went well. \u00a0I 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. \u00a0I pointed the class to Jeff Erickson’s notes on the topic<\/a>, but used the 4 Bill’s<\/a> treatment of matroids in preparing the lecture. \u00a0The problem solving session for this topic (yesterday), on the other hand was … well, the questions were too difficult. \u00a0Yes, I’ve made this mistake before. \u00a0But this time 4 of the 6 questions ended up being too difficult (for the time given). \u00a0Oh well.<\/p>\n

I think I will teach matroids again in this class. \u00a0In 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. \u00a0It’s also a level of abstraction that hasn’t been included in this class before. \u00a0A healthy dose of it, I think.<\/p>\n

Next up, dynamic programming. \u00a0Maybe I’ll include Courcelle’s Theorem. \u00a0(No, I won’t.)<\/p>\n","protected":false},"excerpt":{"rendered":"

In my grad algorithms class, I taught matroids. \u00a0This was last Thursday and came on the heels of a class and problem solving session on greedy algorithms. \u00a0The class, I think, went well. \u00a0I went slowly (Socratically), building up the definition of a matroid using the graphic matroid as an example, motivated by Kruskal’s algorithm […]<\/p>\n","protected":false},"author":3747,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[106166,106190,1000],"class_list":["post-747","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-grad-algorithms","tag-tcs","tag-teaching"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/747","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/users\/3747"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/comments?post=747"}],"version-history":[{"count":1,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/747\/revisions"}],"predecessor-version":[{"id":871,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/posts\/747\/revisions\/871"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/media?parent=747"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/categories?post=747"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/glencora\/wp-json\/wp\/v2\/tags?post=747"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}