Thursday, May 20, 2010

Teaching for the first time: SUBRUK's story

(Guest Post by Subrahmanyam Kalyanasundaram)

My First-time Teaching Experience.

Background: This spring semester, here at Georgia Tech, I got the opportunity to be the full instructor for Automata and Complexity, CS 4510 -- a senior level undergraduate course. I learned about it last summer and started preparing for it during the fall semester. It isn't that common for Ph.D students here in computing to teach a full course, so I was very excited about this class. The course outline, was the following -- regular languages and finite automata, context free languages and pushdown automata, Turing machines, Turing recognizable and decidable languages, undecidable languages, classes P, NP and NP completeness, classes L, NL, NL completeness, NL = co-NL, and PSPACE completeness. If you read Sipser, these are chapters 1, 2, 3, 4, 5, 7 and 8 (with some minimal additions/deletions). These were the material that I was expected to cover.

Beginning: As a student instructor, and since I was doing the class for the first time, I was unsure of how much time (more or less) I would have. I was also a bit nervous. In the beginning of the semester, I didn't know if I would be able to do all of the above topics. So I thought I shall try to not cover anything extra till I got an idea of my pace. In the past I held office house. But this is very different from a class. During office hours, I have the student's attention, and can explain again and again till the student gets it. I didn't have any pressure to finish teaching within a given time. But 2-3 classes into this semester, I realized that I don't have that luxury now. I was responsible for the whole class, and it became imperative that I get the explanation right the first time, or at least mostly right. I realized that good preparation was essential.

The Class: The class had around 20 students. I quickly learned all their names and that helped me develop a rapport with the class. I started teaching the material rather slowly, because I didn't know the level of the students. I soon learned their comfort level and paced myself better. By mid semester, I had finished decidability theory and started on time complexity, which was better than what I had hoped for in the beginning of the semester. So I could afford to do spend more time on the rest. Another thing that I tried to do was to ask the students for feedback at a regular frequency. I tried my best to let them know that they are welcome to air whatever views they have about the class.

I tried to do more examples in the latter half of the class. Also, I did certain things differently from the Sipser book. To give an example, I covered space complexity a bit differently from Sipser. I preferred defining the space bounded TM with a separate worktape up front. Sipser does it after PSPACE completeness, when defining classes L and NL. Plus we covered L, NL, NL completeness, Savitch's theorem and NL = co-NL before concluding with PSPACE completeness. I finished this with some 2-3 classes left, in which I taught the definition of communication complexity, and a few lower bounding methods. Why communication complexity? I felt that the students are much more likely to see randomized classes in future classes. So it was just a choice between interactive proofs and communication complexity, a choice I left to the students at the end. I did interact with GASARCH after his earlier post on what I should cover during the extra lectures, but I didn't use any of his suggestions. For someone who is interested in how I paced my lectures, look at the class schedule.

Exams: We had 2 mid term exams in addition to the final exam. I didn't do a good job of judging the difficulty before the first mid term exam. As a result, there lots of students who were unhappy. I didn't want them to feel demotivated, and wanted to encourage them to continue performing well in the class. So I asked H Venkateswaran, who had the experience of teaching this class before, how I could offer the students a chance to improve their scores. We discussed, and came up with the idea of an optional reading assignment, for those who wanted to improve. This worked well, the students were in general happy for the chance, also they got an opportunity to learn additional material.

Overall: It was a wonderful experience for me overall. Really satisfying, and was worth all the effort that I put into it. And I think most of the students returned happy too, at least those who cared to tell me. It would be incomplete if I didn't thank H Venkateswaran who helped me prepare for the course all through last Fall in a very comprehensive manner, and was readily available to answer my queries of all kind throughout the course. And thanks to my advisor Dick Lipton who was very supportive and understanding all throughout. Finally, I had great students, teaching is very interactive, and the class would have been much less fun if not for them.


  1. Subruk is a great teacher. He has set a loacl standard of excellence.

  2. Subruk rules!

  3. you got lucky

    they let you get to the second test

  4. Three cheers for Subruk!

  5. i just taught more or less the same class (out of Sipser) at UMass Amherst:

    I spent the last third of the course on complexity while you spent the last half, but I agree with you about switching logspace and PSPACE in Sipser. I did a little bit on circuits at the end where you did communication complexity -- both are reasonable choices.

    I'm impressed with your process for the course --you will make a great teacher of undergraduates.

  6. Dave, Dick : Thanks for your kind words.

    Dave : I have looked at your class website to get a general idea on how to go about the class, and also to get an idea of candidate HW problems.

  7. teaching is a pain in the behind, I tell you that...