CS 365 Models of Computation
Watch a video introduction to this course on YouTube.
Objectives
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.
Intended Audience
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.
Related Courses
Prerequisites: CS 240, 241 and (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.
References
Introduction to the Theory of Computation, by Sipser, Thomson Course Technology, second edition, 2006.
Schedule
3 hours of lectures per week. Normally available in Winter.
Outline
Finite Automata (6 hours)
Equivalence of NFAs and DFAs. Equivalence with regular expressions. The pumping lemma and applications.
Context-free Grammars (4 hours)
The pumping lemma for CFLs and applications. Equivalence with pushdown automata.
Turing Machines and Undecidability (8 hours)
Church-Turing thesis. The halting problems. Reductions to prove undecidability.
Time Complexity (3 hours)
Robustness. The classes P and NP. A sketch of NP-completeness.
Space Complexity (6 hours)
Savitch's Theorem. PSPACE, L, NL: complete problems and closure properties.
Intractability (6 hours)
Diagonalization and hierarchy theorems.
Advanced Topics (3 hours)
A brief look at topics chosen by the instructor, such as probabilistic or parallel complexity classes.
