CS 365: Models of Computation
University of Waterloo, Winter 2017
- Winter 2017
- Time: Tuesdays and Thursdays, 10:00-11:20am
Location: MC 4064
Office hours: Tuesdays, 11:30am-12:30pm in DC 3122
- Teaching assistant
- Nathan Harms
Office hours: Mondays, 1-2pm in DC 2305
- Piazza page
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.
Michael Sipser's Introduction to the Theory of Computation is the primary textbook for the class and is required.
In the second half of the course, we will also cover material that is found in
Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach. That textbook is recommended but not required.
- Regular languages
- Finite automata, DFAs, NFAs, Regular expressions, Pumping lemma
- Context-free languages
- Pushdown automata, context-free grammars, Chomsky normal form
- Turing machines, undecidability, Halting problem, reductions
- Time complexity
- P and NP, NP-completeness, Time hierarchy theorem.
- Space complexity
- L, NL, PSPACE, polynomial hierarchy.
- Circuit complexity
- P/poly, Shannon's lower bound, bounded-depth circuits