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