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

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.

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!

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.

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.