Tag Archives: grad algorithms

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

Inoffensive stable matching

I like to start my grad algorithms course with stable matching.  It is a beautiful, clean, practical algorithm.  It can be covered relatively quickly and give an overview of the basics of algorithm design and analysis.  I love it.

What I hate is that every treatment of stable matching available online and in the textbooks in my office is presented as the stable marriage problem with men getting matched to women and men getting their best possible match and women getting their worst possible match.  Seriously?  This algorithm that is used to match children to schools and medical students to residency programs and dental and medical specialists to hospitals and students to universities and lawyers to law firms and rabbis to congregations (or so I’ve been told)?  We need to teach this algorithm as an exercise in heternormative, sexist coupling?

If half our field were women, do you think women would be repeatedly getting the shaft in this lesson plan?  If we didn’t need It Gets Better in our society, would we be proscribing to man meets woman, man proposes to woman, man marries woman?  If we lived in a dreamy society that didn’t spend one-third of Africa’s debt each year in the wedding industry, would we be using this metaphor?

So, here you go: very basic, stripped-down lecture notes on the Gale-Shapely algorithm that matches jobs to candidates.  (Written quickly, corrections welcome.)

If someone could change the wikipedia page on the problem from stable marriage to stable matching, I would be much appreciative.  (My wikipedia skills are no match.)

Update 9/22: To clarify, it is the United States that spends (on the wedding industry) an amount equivalent to one-third of Africa’s debt.

Update 9/25: Jeff Erickson presents stable matching using doctors and hospitals.

Update March 2015: Motherboard picks up the story.

Lecture notes for Baker's technique for PTASes in planar graphs

In teaching so far, I have relied almost exclusively on textbooks and other people’s lecture notes (Jeff Erickson comes to mind, again and again) for providing materials to my students.  Yes, I would recommend this to anyone who has not been teaching for too long.  Preparing lecture notes that are hand-out-to-your-students worthy is time consuming!  Especially when you are a perfectionist.

I’m teaching a grad course on approximation algorithms right now, using Vijay Vazirani’s book.  (Yes.  Those of us on the quarter system are still teaching.)  I wanted to teach Baker’s technique for giving PTASes on planar graphs as it is beautiful and close to my heart.  By heart, I mean brain.  I only wanted to spend a lecture or two on it and my students don’t know what treewidth is.   The only lecture notes on this that I know of are Philip Klein’s and (stubbornly), I needed something more self-contained – that didn’t build on a course’s worth of notation and background.

So, I prepared these notes on my wiki teaching page.  I don’t prove that k-outerplanar graphs have treewidth 3k-1 or even define treewidth, but I show a simpler version of solving maximum-weight independent set on something I call k-innerplanar graphs.  I think it gives the intuition and ingredients of the full picture without getting caught up in too many details.  If anyone spots a bug, inconsistency, etc, please let me know.

So, yes, basically I am announcing “Ooooh look at me!  I’m doing something everyone else has already done time and time again!”

Experiments in teaching: am-I-ready-for-this? quiz followup

One of my experiments in teaching this quarter was to have a quiz the second week of class on material that I considered so basic, that if you couldn’t do very well on the quiz, well, you may well consider (re-)taking the undergrad algorithms course first.  A few students with lower scores on the quiz did decide to drop the class.  Well, term is over now and I can see how good an indicator this quiz was.

Shown below are the student grades on the midterm and final (y-axis, midterm ‘o’ and final ‘*’)  vs the quiz score (z-axis) – plots are linear.  The brighter the shade of green for the vertical bar connecting a students exam scores, the higher the final grade for the student.  While there are a few outliers, I think that I wasn’t wrong in saying that a low score on the quiz may indicate that you aren’t ready for grad algorithms.  What you can’t see as well here is that the midterm scores were quite linear with the quiz – not as surprising as the midterm covered material that I would expect starting CS grad students to know anyway.

So I’ll probably do this again next year.  I’m better informed though.  I’d like to include a few harder questions to give a better indication of mathematical maturity than this year’s version provided.  My goal?  A perfect indicator, so that I can skip all forms of evaluation and simply assign the students a grade based on the first quiz.

Experiments in teaching: problem-solving sessions

In a more significant experiment than the am-I-ready-for-this quiz, I am rethinking the assignments that accompany my grad algorithms course.  In last year’s class, I had the grad students work in randomly-assigned and rotating (different for each assignment) groups.  I will comment on this in another post.

I’m sticking with the group-based approach – partly for feasibility.  But rather than having standard written submissions and written comments/grades, I am having the students participate in a type of problem-solving session; and idea I stole from Claire Mathieu.

Each group will prepare solutions to some (2) problems ahead of the 2-hour problem-solving session.  Each group (A) will explain the solution to one of their problems X (picked by me) to another group (B) who will then explain the solution to me, with instant feedback/help/cleaning. Group B should leave the session satisfied that they understand the solution to X and will prepare a written solution within 2 days.  The grade of both group A and B will depend on the oral explanation I was given and the written solution to problem X.  Every group will take the role of teacher/student for one problem (that is, group B will then explain the solution to one of their problems, Y, to group A).  The written solutions will be placed into a (private-to-OSU) repository for other groups to see.  For details, see here.

Students are encouraged to repeat this process for other problems that they did not solve or learn; there are as many problems as groups (12) and every student knows who has solved each problem.  I’m hoping this will be a helpful, less lonely, way for them to prepare for the midterm and final (which will determine the bulk of their grade).

I’m hoping that this will help students learn to solve the types of problems they will be asked on the midterm and exam, and (more importantly) that they might face in their research (or in job interviews).  I’m also hoping that it is a more effective use of class time than hearing me lecture for another 2 hours a week. (I have 4 total hours per week of class time).

As before, I will (bravely) ask my students to comment.  I will try and do my best to take the comments into consideration to improve the remaining 5 problem solving sessions.  I have already received one comment that will take effect next session: in the last session, some problems went undiscussed; in future sessions, every problem will be discussed (by some pair of groups) and posted to the repository.  Comments from non-students are always appreciated!

Experiments in teaching: am-I-ready-for-this? quiz outcome

Last week, I gave the students in my grad algorithms class an am-I-ready-for-this? quiz.  I promised to report back, and I’m already a little late on that.  The average for the quiz was ~ 70% – I was hoping for a higher average, given how easy the quiz was (in my opinion).  Two students did not take the quiz (and have dropped the class) and two students (who were in the bottom 10%) did drop the class; so perhaps the quiz had the intended effect.

I am more interested in hearing what the students in my class have to say, though.  So, I’m opening up the comments to them:  Was the quiz useful?  Did you study for the quiz?  How could I make the quiz more useful?  I will try to use this feedback in future years, so please be honest.  Feel free to respond anonymously with a fake email and fake name.

Experiments in teaching: am-I-ready-for-this quiz

I am teaching ‘the grad algorithms course’ for the second time.  It is the first time I am teaching a course for the second time and am excited at finally having the opportunity to fix my previous mistakes.  ‘The grad algorithms course’ is required for all CS Ph.D. students in our department and a prerequisite for any other grad course that I teach.  Last year I had ~30 students.  This year I expected the same, if not less, since I heard that grad enrolment was high last year and low this year.  But no.  First the 35 slots filled up.  Then the 10 slot waiting list filled up.  Then they raised the cap (complete with room change 3 days before term) to 45.  Then the class filled up again.  Cap raise + room change to 49 the day before class.  STOP!

Enrolment has waned back down to 38.  Perhaps at least partly due to my first experiment in teaching, the am-I-ready-for-this quiz.

Last year I was a softy.  Don’t think you have the background for the class?  Give it a try! Come by my office, I’ll bring you up to speed.

I’m not doing that this year.  Sure it will probably save me some time, but mostly I think (hope) it is more fair to the students in the class who do have the background.  So on the first class of the second week, I am giving a quiz on material that is either (a) standard and easy undergraduate algorithms material or (b) very easy for someone to learn in roughly one hour of reading given standard undergraduate algorithms material.  My motivation was from Jeff Erickson’s Homework Zeroes and has the goal of:

  • Formally letting the students know that even though this course may be required for their program and they were accepted to the program, they may need to do some work before attempting the course.
  • Getting the students thinking about algorithms and paging back in their (fond) memories of undergrad algorithms.
  • Getting the students reading material, learning the lingo (particularly if their undergrad courses were not taught in English) before we get into the harder material in the class.

The quiz is next week. I’ll try and remember to report back on how it went.