Revised August 13, 2014
CS 365: Models of Computation
Watch a video introduction to this course on YouTube.
General 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. The course also covers topics from complexity theory including time and space complexity, hierarchy theorems, and complete problems for various classes.
Logistics
Audience
- CS major students
Normally available
- Winter
Related courses
- Pre-requisites: CS 240, 241, 245, MATH 239 or 249
- Successors: CS 462
- Anti-requisites: CS 360
CS 365 may be substituted for CS 360 in any degree plan or for pre-requisite purposes.
For official details, see the UW calendar.
Software/hardware used
- None
Typical reference(s)
- Introduction to the Theory of Computation, third edition, Sipser, Thomson Course Technology, 2012
Required preparation
At the start of the course, students should be able to
- Understand what a proof is
- Create proofs by induction
Learning objectives
At the end of the course, students should be able to
- Describe how a real computer can be modeled mathematically by a theoretical computer in many different ways
- Explain what a formal language is and how it corresponds to a computational decision problem
- Describe regular languages in two different ways (automata and regular expressions)
- Describe context-free languages in two different ways (grammars and pushdown automata)
- Prove languages regular and non-regular, context-free and non-context-free, recursive and non-recursive, recursively enumerable and non-r.e.
- State the Church-Turing thesis
- Explain what nondeterminism is and how it is used
- Explain what a Turing machine is and create simple Turing machines to solve problems
- Describe the fundamental limits to computation (computable versus uncomputable)
Typical syllabus
Finite automata (6 hours)
- Equivalence of NFAs and DFAs
- Equivalence with regular expressions
- Pumping lemma and applications
Context-free grammars (4 hours)
- Pumping lemma for CFLs and applications
- Equivalence with pushdown automata
Turing machines and undecidability (8 hours)
- Church-Turing thesis
- Halting problems
- Reductions to prove undecidability
Time complexity (3 hours)
- Robustness
- Classes P and NP
- 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)
- Various topics chosen by the instructor, such as probabilistic or parallel complexity classes
