CS 365: Models of Computation
University of Waterloo, Winter 2017

Course Information

Term
Winter 2017

Lectures
Time: Tuesdays and Thursdays, 10:00-11:20am
Location: MC 4064

Instructor
Eric Blais
eric.blais@uwaterloo.ca
Office hours: Tuesdays, 11:30am-12:30pm in DC 3122

Teaching assistant
Nathan Harms
Office hours: Mondays, 1-2pm in DC 2305

Syllabus
Here.

Piazza page
Here.

Description
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.

Assignment 1.
Due on Jan 12. (Solution template)
Assignment 2.
Due on Jan 19. (Solution template)
Assignment 3.
Due on Jan 26. (Solution template)
Assignment 4.
Due on Feb 2. (Solution template)
Assignment 5.
No solution needs to be handed in for this assignment.
Assignment 6.
Due on Feb 16. (Solution template)
Assignment 7.
Due on Mar 9. (Solution template)
Assignment 8.
Due on Mar 16. (Solution template)
Assignment 9.
Due on Mar 23. (Solution template)
Assignment 10.
Due on Mar 30. (Solution template)

List of topics

Regular languages
Finite automata, DFAs, NFAs, Regular expressions, Pumping lemma
Context-free languages
Pushdown automata, context-free grammars, Chomsky normal form
Computability
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

Cover photo of Babbage's Difference Engine #2 ©Giles Moss.
Site designed with Bootstrap.