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.
Textbooks
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.
Assignments
The assignments will be added here as they become available. All assignments are to be submitted in class at the beginning of lecture on their due dates.