## Thursday, December 27, 2007

### Oral Homework

This fall in my graduate complexity courses 5/11 of the HW were group HWs. This means that
1. The students are in groups of 3 or 4. The groups are self-selected and permanent (with some minor changes if need be).
2. The groups do the HW together.
3. They are allowed to use the web, other students, me, other profs.
4. The HW is not handed in–they get an Oral Exam on it.
5. The HW is usually "read this paper and explain this proof to me."
In my graduate course in Complexity Theory which I just finished teaching 5 out of the 11 HWs were Oral HW. Here is what they were basically:
1. Savitch's theorem and Immerman-Szelepcsenyi Theorem.
2. Show that VC and HAM are NPC.
3. E(X+Y)=E(X)+E(Y), Markov, Chebyshev, Chernoff
4. Reg Exp with squaring NOT in P.
5. Matrix Group Problem in AM. (Babai's paper "Trading Group Theory for Randomness").
1. The students learned ALOT by doing this. They learned the material in the paper, they learned how to read a paper, and they learned how to work together. (Will all of these lessons stick?)
2. Some proofs are better done on your own than having a professor tell you them (HAM cycle NPC comes to mind). This is a way to make them learn those theorems without me having to teach it.
3. Some theorems are needed for the course, but are not really part of the course (Chernoff Bounds come to mind). The Oral HW makes them learn that.
4. This was a graduate course in theory so the students were interested and not too far apart in ability. This would NOT work in an ugrad course if either of those were false.
5. This course only had 19 students in it, so was easy enough to administer.
So the upshot–It worked! I recommend it for small graduate classes.

1. This was a graduate course on complexity?! Items 2 and 3 students should have been expected to know (learn) on their own, and items 4 and 5 are ok level of difficulty but a bit non-standard...

2. Reg Exp with squaring NOT in P.

This problem is in P, if I remember correctly. What isn't in P is the equivalence of regular expressions with squaring.

3. This post reminded me of a paper I read recently as part of a teaching pedagogy program at my school (an add-on to my PhD program):

Goldberg, D. J. (1981). "Problem solving in small groups."

It discusses and highly recommends an approach similar to what's described here, for first-year math courses.

One thing that paper strongly endorses is an "icebreaker" where, e.g., students interview each other in pairs and report back to the class, in fact Goldberg says

Even if group work had not been initiated, the socializing exercise would have been a worthwhile activity for both students and instructor.

I'm convinced that it's worth trying next time I teach a non-huge class but I never participated in one of these as an undergrad. Have readers of this blog had any experience with icebreakers in math/CS courses?

4. This works really well. The class size has to be small, but assuming that, the academic level is irrelevant -- this works for students well before grad school.

5. Another good reason for this style of teaching/hw: it can lead to partnerships that last way beyond the length of the course. (I believe Louis can attest to this as well, if he's who I think he is).

6. We did the same thing in an undergrad course on algorithms, even though the class was pretty large. Then again, the TAs did proof evaluations, too, so there were more graders to go around.

7. Was this post really by Lance? A quick glance at the U. Chicago CS website reveals that Lance did not in fact teach a complexity course (graduate or other) in Fall 2007. Bill Gasarch, on the other hand, did teach such a course, and it in fact had 11 homeworks... I assume this was just some sort of typo.

8. (I feel silly posting this since its 4 years later).
YES, this was a BILL post. So was the post on WHICH PRESIDENTS KNEW THE MOST MATH. There is a glitch so that all posts before a certain date are
labelled Lance even if bill did them. Usually its easy to tell if its
a bill-post.

9. (I feel silly posting this since its 4 years later).
YES, this was a BILL post. So was the post on WHICH PRESIDENTS KNEW THE MOST MATH. There is a glitch so that all posts before a certain date are
labelled Lance even if bill did them. Usually its easy to tell if its
a bill-post.