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.

  • 2
    $\begingroup$ 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. $\endgroup$ Mar 14, 2013 at 15:21
  • $\begingroup$ 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. $\endgroup$
    – Shaull
    Mar 14, 2013 at 15:24
  • 1
    $\begingroup$ Option 3 is confusing. I do not see the connection between IP = PSPACE, communication complexity, and coNP in PSPACE (which is trivial) $\endgroup$ Mar 14, 2013 at 16:05
  • $\begingroup$ 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). $\endgroup$
    – Shaull
    Mar 14, 2013 at 16:12

1 Answer 1


If I'm a student, I would've liked to learn more about other computational models (primarily, lambda calculus and recursive functions). More and more programming languages are incorporating functional features, and learning these subjects would give a great insight into this perspective of thinking about computation.

  • $\begingroup$ Interesting idea. Recursive functions are available to the students in the scope of a logic course, so we don't feel a need to cover it. Lambda calculus is an intriguing possibility. $\endgroup$
    – Shaull
    Apr 17, 2013 at 5:14
  • $\begingroup$ In some Universities Functional programming (CAML, Objective CAML, and python in some sense) is the first programming language taught to the students! $\endgroup$
    – Jérémy
    Apr 17, 2013 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.