Watch a video introduction to this course on YouTube.
This course provides accelerated coverage of the material from CS 360, including finite automata and regular languages, context free grammars and pushdown automata, Turing machines, and undecidability. In addition, topics from complexity theory are covered, including time and space complexity, hierarchy theorems, and complete problems for various classes.
Undergraduates with solid mathematical skills and an interest in learning more about the theory of computation. This course may be used as a substitute for CS 360 wherever it is required in Honours CS programs.
Prerequisites: CS 240, 241, 245, MATH 239 or 249; Computer Science students only.
Antirequisites: CS 360.
Successors: CS 462.
CS 365 may be substituted for CS 360 in any degree plan, or for prerequisite purposes.
Introduction to the Theory of Computation, by Sipser, Thomson Course Technology, second edition, 2006.
3 hours of lectures per week. Normally available in Winter.
Equivalence of NFAs and DFAs. Equivalence with regular expressions. The pumping lemma and applications.
The pumping lemma for CFLs and applications. Equivalence with pushdown automata.
Church-Turing thesis. The halting problems. Reductions to prove undecidability.
Robustness. The classes P and NP. A sketch of NP-completeness.
Savitch's Theorem. PSPACE, L, NL: complete problems and closure properties.
Diagonalization and hierarchy theorems.
A brief look at topics chosen by the instructor, such as probabilistic or parallel complexity classes.
David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
Tel: 519-888-4567 x33293
Fax: 519-885-1208
Contact | Feedback: cs-uops@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics
Last modified: Tuesday, 14-Feb-2012 11:29:15 EST
