Sorry, an error occurred while loading the content.
Browse Groups

• ## [Computational Complexity] Oral Homework

(1)
• NextPrevious
• 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
Message 1 of 1 , Dec 27 4:05 AM
View Source
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.

--
Posted By Lance to Computational Complexity at 12/27/2007 06:02:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.