CS 360 Introduction to the Theory of Computing

Watch a video introduction to this course on YouTube.


To give a basic introduction to the theoretical foundations of computer science.

Intended Audience

Some exposure to the theoretical foundations of Computer Science is considered useful for all CS graduates, especially for anyone intending to continue studies at the graduate level.

Related Courses

Prerequisites: CS 240, 241 and (MATH 239 or 249); Computer Science students only.

Antirequisites: CS 365.

Successors: CS 462.


Introduction to Automata Theory Languages & Computation 3rd ed., by Hopcroft, Motwani & Ullman, Published by: Addison Wesley (required)


3 hours of lectures per week. Normally available in Fall, Winter and Spring


Finite Automata (10 hours)

Deterministic and non-deterministic finite automata and their equivalence. Equivalence with regular expressions. Closure properties. The pumping lemma and applications.

Context-free Grammars (10 hours)

Definitions. Parse trees. The pumping lemma for CFLs and applications. Normal forms. General parsing. 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)

The undecidability of the halting problem. Reductions to other problems. Reduction in general.