Teaching end-course material in a computational-models course

manpreet Best Answer 2 years ago

As TAs in an undergrad course on computational models, every year we are faced with a dilemma of what material to teach in the last few weeks of the course.

To be specific, our typical syllabus is as follows (basically the first few chapters of Sipser):

1. Finite Automata: DFA, NFA, determinization, Myhill-Nerode, etc.

2. Turing Machines: computability (RE,R, mapping-reductions, undecidability results).

3. Complexity classes: P, NP, PSPACE, karp-reductions, Savitch's theorem, Time/Space Hierarchy theorems.

Now comes the question of what to do next (usually we have about 3 weeks left).

Option 1: NL, coNL, logspace reductions and the Immerman Zzelepcsényi theorem.

Option 2: Randomized complexity (RP, BPP), but in a very low level, since probability is not a prerequisite for the course.

Option 3: Communication complexity - describing a communication model with some very initial results, describing IP and trying to prove 

manpreet 2 years ago