<p>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.</p>

CC BY-SA 3.0
2013-04-17T05:14:27.440Z
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.
Shaull
CC BY-SA 3.0
2013-04-17T08:34:27.340Z
In some Universities Functional programming (CAML, Objective CAML, and python in some sense) is the first programming language taught to the students!
J.y B.y
CC BY-SA 3.0
2013-04-16T21:00:52.833Z
2013-04-16T21:00:52.833Z
Haitham Gad
<p>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. </p>

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

<ol>
<li><p>Finite Automata: DFA, NFA, determinization, Myhill-Nerode, etc.</p></li>
<li><p>Turing Machines: computability (RE,R, mapping-reductions, undecidability results).</p></li>
<li><p>Complexity classes: P, NP, PSPACE, karp-reductions, Savitch's theorem, Time/Space Hierarchy theorems.</p></li>
</ol>

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

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

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

<p>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$.</p>

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

<p>Other options are welcome.</p>

<p><strong>The question</strong>, to be as precise as possible, is as follows:</p>

<p>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)?</p>

<p>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.</p>

CC BY-SA 3.0
2013-03-14T15:21:43.920Z
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
CC BY-SA 3.0
2013-03-14T15:24:22.667Z
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
CC BY-SA 3.0
2013-03-14T16:05:53.837Z
Option 3 is confusing. I do not see the connection between IP = PSPACE, communication complexity, and coNP in PSPACE (which is trivial)
Sasho Nikolov
CC BY-SA 3.0
2013-03-14T16:12:04.953Z
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
<cc.complexity-theory><teaching>
Teaching end-course material in a computational-models course
Shaull
# Teaching end-course material in a computational-models course

(Asked by: username_0 on 2013-03-14)

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.

**Tags:** cc.complexity-theory, teaching
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: Option 3 is confusing. I do not see the connection between IP = PSPACE, communication complexity, and coNP in PSPACE (which is trivial)  
> **username_0**: 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).  

---

## 1 answers

### Answer by username_3 on 2013-04-16. Score: 4

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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: In some Universities Functional programming (CAML, Objective CAML, and python in some sense) is the first programming language taught to the students!  

---

