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