Revised Sept 18, 2014
CS 360 Introduction to the Theory of Computing
Watch a video introduction to this course on YouTube.
General description
This course introduces the theoretical foundations of Computer Science.
Logistics
Audience
- CS major students and especially students interested in graduate school
Normally available
- Fall, Winter, and Spring
Related courses
- Pre-requisites: CS 240 or SE 240, CS 241, MATH 239/249 or CO 103, CS 245 or SE 112/212
- Successors: CS 462
- Anti-requisites: CS 365
For official details, see the UW calendar.
Software/hardware used
- None
Typical reference(s)
- Introduction to Automata Theory Languages & Computation, 3rd ed., Hopcroft, Motwani, & Ullman, Prentice Hall, 2009
Required preparation
At the start of the course, students should be able to
- Describe 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.
- Describe 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 (10 hours)
- Deterministic and non-deterministic finite automata and their equivalence
- Equivalence with regular expressions
- Closure properties
- Pumping lemma and applications
Context-free grammars (10 hours)
- Definitions
- Parse trees
- Pumping lemma for CFLs and applications
- Normal forms
- Sketch of equivalence with pushdown automata
Turing machines (9 hours)
- Designing simple TMs
- Variations in the basic model (multi-tape, multi-head, non-determinism)
- Church-Turing thesis and evidence to support it through the study of other models
Undecidability (7 hours)
- Undecidability of the halting problem
- Reductions to other problems
- Reduction in general