# Teaching end-course material in a computational-models course

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 $IP=PSPACE$, but usually only getting up to $coNP\subseteq IP$.

Option 4: Kolmogorov complexity. (we haven't tried this one yet).

Other options are welcome.

The question, to be as precise as possible, is as follows:

Assuming that at least 50% of the undergrads are not interested in theory, and that most of them will not continue to grad school, what would be most fitting, so as to teach interesting material (i.e. less definitions, more theorems), while keeping it somewhat relevant to other disciplines in CS (or, heaven-forbids, the industry)?

My personal answer: I think that NL is a good option - theoretically it is interesting since we have some impressive results (NL=coNL), and practically it is interesting since many exponential time algorithms can be composed with NL algorithms to produce PSPACE algorithms (e.g. NFA universality). On the other hand, one might argue that it is more important to get acquainted with randomized algorithms.

• Since you are trying to accommodate undergraduate students who are not interested in theory and probably graduate and look for position in industry, may I suggest a new option of an introduction to approximation algorithms for practical optimization problems and some associated hardness results. – Mohammad Al-Turkistany Mar 14 '13 at 15:21
• Approximation algorithms are actually taught in an "algorithms" course, which is a prerequisite. Hardness of approximations would have been great to teach, but I fear interesting results there are too hard. – Shaull Mar 14 '13 at 15:24
• Option 3 is confusing. I do not see the connection between IP = PSPACE, communication complexity, and coNP in PSPACE (which is trivial) – Sasho Nikolov Mar 14 '13 at 16:05
• Sorry, I edited the post. We prove $coNP\subseteq IP$. As for the connection - after describing a communication model, you can go both toward communication complexity and toward IP. Not completely related, but still both talk about complexity in the presence of communication. Other options in this context could be zero-knowledge proofs (but the formal model is too complicate for students, even though it is very easy to demonstrate). – Shaull Mar 14 '13 at 16:12