This fall in my graduate complexity courses 5/11 of the
HW were group HWs. This means that
The students are in groups of 3 or 4. The groups are
self-selected and permanent (with some minor changes
if need be).
The groups do the HW together.
They are allowed to use the web, other students, me,
The HW is not handed in–they get an Oral Exam on it.
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:
Savitch's theorem and Immerman-Szelepcsenyi Theorem.
Show that VC and HAM are NPC.
E(X+Y)=E(X)+E(Y), Markov, Chebyshev, Chernoff
Reg Exp with squaring NOT in P.
Matrix Group Problem in AM. (Babai's paper "Trading Group
Theory for Randomness").
Was this a good idea?
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?)
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.
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.
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.
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.
Posted By Lance to Computational Complexity
at 12/27/2007 06:02:00 AM