CS420: Introduction to the Theory of Computation
Credits: 3
Catalog Description
Introduction to theoretical aspects of computing including models of computation, inherent limits on computation, and feasible computation. Topics studied will include definition of computable functions (recursive functions, functions computable by Turing machines, functions computable in a programming language), insolvability of the halting problem and related problems, the classes P and NP, finite automata, and context-free grammars.
Current & Upcoming Offerings
2025-2026
Fall 2025 2 sections
| Section | Schedule / Time | Instructor | Location |
|---|---|---|---|
| 01 |
MW 04:00PM - 05:15PM
|
De Blois, Jane Holly |
W01-0005
|
| 02 |
MW 02:30PM - 03:45PM
|
Chang, Stephen T |
W01-0005
|
Spring 2026 2 sections
| Section | Schedule / Time | Instructor | Location |
|---|---|---|---|
| 01 |
MW 04:00PM - 05:15PM
|
Sepahyar, Soheil |
Y02-2330
|
| 03 |
TuTh 04:00PM - 05:15PM
|
Sepahyar, Soheil |
M02-0116
|
Prerequisites
- CS 220/CS 320L
Notes
This course is required for all computer science majors who took CS 220/CS 320L during fall 1989 or later. It may be used as a theoretical elective by other computer science majors.
Textbooks
Title: Introduction to the Theory of Computation
Author(s): Michael Sipser
Publisher: Course Technology
Edition: 3rd
ISBN: 113318779X
Introductory course in the theory of computation for advanced undergraduates covering computability, automata, and formal language theory.