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):
Finite Automata: DFA, NFA, determinization, Myhill-Nerode, etc.
Turing Machines: computability (RE,R, mapping-reductions, undecidability results).
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.
