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