Why CS 483 has changed

When CS 483 was taught in Spring 2000 and Spring 2001, it had the following list of topics (taken from chapters 0, 1, 2, 3, 4, 5, 7, 8 of the text by Sipser):

Proof techniques
Finite automata, nondeterminism, regular expressions
Nonregular languages
Context-free grammars, pushdown automata
Noncontext-free languages
Turing machines
Decidability, Halting problem
Reducibility, undecidable problems
Time classes: P, NP, NP-complete
Space classes
The course was very successful, except that some students (rightly) pointed out that it duplicated material on regular languages and machines and context-free languages and pushdown automata that they had studied in CS 352. Furthermore, in the 2001-2002 academic year, the department introduced CS 182, which included material on proof techniques and an introduction to regular languages and machines and context-free languages and pushdown automata. At the same time, many students expressed an (unanticipated) enthusiasm for topics covered late in the course, especially space complexity and its relationship to games. This reflected the very accessible manner in which the Sipser text treated these topics. It now seems that good undergraduates are able to handle this material.

When CS 483 was taught in Fall 2002, the department was dealing with increasing enrollment pressures and the desire to teach courses in emerging and expanding areas. Thus CS 483 and CS 584 were offered together. However, the mix of undergraduate and graduate students pushed the level at which the course was taught a bit too high for the undergraduates. In Fall 2004, CS 483 was offered by itself, so that the course could be taught at a level appropriate for advanced juniors and seniors. This latter approach seemed to work well and will be followed this time too.

The current version of CS 483

CS 483 course will cover the following topics (taken from sections 1.4, 2.2, 2.3 and from chapters 3, 4, 5, 6, 7, 8, 9, 10 of the text):

Pumping lemmas
Equivalence of PDAs and CFGs
Turing machines and the Church-Turing thesis
Decidability, Halting problem
Reducibility, Undecidable problems
Decidability of logical theories, Kolmogorov complexity
Time classes: P, NP, NP-complete
Space classes: Savitch's theorem, PSPACE-completeness, NL-completeness
Approximation algorithms, Probabilistic algorithms
Parallel Computation, Cryptography
Thus the course will focus primarily on computability theory (chapters 3-6) and complexity theory (chapters 7-10). The instructor reserves the right to trim topics as necessary.