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
selfselected 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,
other profs.

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 ImmermanSzelepcsenyi 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.
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 nonstandard...
ReplyDeleteReg Exp with squaring NOT in P.
ReplyDeleteThis problem is in P, if I remember correctly. What isn't in P is the equivalence of regular expressions with squaring.
This post reminded me of a paper I read recently as part of a teaching pedagogy program at my school (an addon to my PhD program):
ReplyDeleteGoldberg, D. J. (1981). "Problem solving in small groups."
It discusses and highly recommends an approach similar to what's described here, for firstyear 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 nonhuge 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?
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.
ReplyDeleteAnother 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).
ReplyDeleteWe 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.
ReplyDeleteWas 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.
ReplyDelete(I feel silly posting this since its 4 years later).
ReplyDeleteYES, 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 billpost.
(I feel silly posting this since its 4 years later).
ReplyDeleteYES, 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 billpost.