I am teaching the undergrad jr/sr course Elementary Theory of Computation
which is Reg Langs, Context free Langs, Computability theory, P and NP.
Over the last few years I've changed some of the content (I dumped CFLs-- don't worry, they cover them some in the Prog Langs course) but more to my point today changed the ORDER I do things in
Change 1: Do P and NP first and Computability later. While this is not historically accurate (which may be why the order was what it was)
this is better pedagogically. Why? Consider the following reductions:
1) Given a FORMULA phi produce a graph G and a number k such that
phi is in SAT iff (G,k) is in CLIQ
2) Given a MACHINE M_e produce a MACHINE M_i such that
M_e(e) halts iff M_j halts on at least 10 numbers.
Students have always found the second more confusing since the input and the output are both machines (and the reduction itself is done by a machine)
where as the first one seems like a REAL transformation- you input a FORMULA
and get out a GRAPH and a NUMBER.
There are two other reasons to do P NP first:
(1) Sometimes the last topic in a course gets short changed, and P NP is
more important than Computability, so better if Computability gets short changed.
(2) Lets say I could do P NP in either April or May. If I do it in April and someone resolves it in May, the students can get excited about it since they know about it. If I do it in May and its resolved in April then the students
cannot share in the joy of the discovery. This reason may become more relevant in the year 2214.
Change 2: I used to do the Cook-Levin Theorem (SAT is NP-complete) and
then do a reduction like SAT \le CLIQ. This semester I did SAT \le CLIQ first
and Cook-Levin later. Why? Because SAT\le CLIQ is better pedagogically (note- pedagogically is today's word on my word-of-the-day calendar) since the Cook-Levin reduction is harder and deals with Turing Machines as opposed to more familiar objects like Formulas and Graphs.
More generally- the order you teach things in may matter, and changing it is relatively easy.
LOL … Ed Witten studied history and linguistics first, then modern mathematics, and quantum physics last.
ReplyDeleteQuestion Do texts like The Feynman Lectures introduce quantum mechanics far too early in the curriculum? Before students are adequately grounded in history and mathematics?
Sipser's book does 3-SAT <=_p CLIQUE before Cook-Levin, on the reasoning that in order to understand the definition of NP-completeness you need a compelling example of a p-reduction. I agree with this.
ReplyDeleteWhen I do computability in the middle third of the "Sipser" course, I am relying somewhat on the fact that our algorithms course is a prerequisite and so they are supposed to have seen NP-completeness to some extent. But our instructors for that course vary in the amount of time they spend on NP-completeness, as well as the level of similarity to computability in their presentation.
I also try to spend a week on Turing machines in the discrete math course that comes before algorithms -- this is enough to give a somewhat hand-wavey proof of the unsolvability of the halting problem.