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