CS 483 - Introduction to the Theory of Computation (Fall 2026)
Course Information
Instructor: Wei Zhan, email: weizhan [AT] purdue [dot] eduMeetings: Tuesday & Thursday, 12:00 - 1:15 PM @ BHEE 236
Office hours: Tuesday 2:30 - 3:30 PM @ DSAI 1100
Course Description
This is an introductory undergraduate level course on the theory of computation. We will cover basic topics in automata theory, computability theory and complexity theory, with the goal to establish the mathematical foundations for modeling and reasoning about algorithms and computation. We will build up a systematic framework for classifying computational tasks, in order to understand why some problems could be intrinsically hard to solve by a computer.Resources
The course is mostly based on the following optional textbook:- (Sip) Introduction to the Theory of Computation by Michael Sipser
- Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak
- Automata, Computability, and Complexity by Scott Aaronson at MIT
- Introduction to the Theory of Computation by Omer Reingold at Stanford
- Introduction to Theoretical Computer Science by Boaz Barak at Harvard
Grading
- Homework (5 highest out of 7 assignments): 10% each, 50% total;
- Midterm exam: 20%;
- Final Exam: 30%.
Course Schedule
Note: the schedule below is tentative and will be updated along the course progression.| Date | Topic | Material | Reading |
|---|---|---|---|
| Tue. Aug 25 | Course overview, finite automata | Lecture 1 | (Sip) 1.1 |
| Thu. Aug 27 | Regular expressions, closure property | Lecture 2, Problem Set 1 (Due: Sep 10) | (Sip) 1.1, 1.3 |
| Tue. Sep 1 | Nondeterministic finite automata | Lecture 3 | (Sip) 1.2 |
| Thu. Sep 3 | Equivalence of NFA and DFA, regular grammars | Lecture 4 | (Sip) 1.2 |
| Tue. Sep 8 | Pumping lemma | Lecture 5 | (Sip) 1.4 |
| Thu. Sep 10 | Myhill-Nerode theorem | Problem Set 2 (Due: Sep 24) | |
| Tue. Sep 15 | Context-free languages | ||
| Thu. Sep 17 | Pushdown automata, Pumping lemma for CFL | ||
| Tue. Sep 22 | Turing machines | ||
| Thu. Sep 24 | Variants of Turing machines | Problem Set 3 (Due: Oct 8) | |
| Tue. Sep 29 | Universal Turing machine, Church-Turing thesis | ||
| Thu. Oct 1 | Decidability, diagonalization | ||
| Tue. Oct 6 | Mapping reductions, Rice’s theorem | ||
| Thu. Oct 8 | Post correspondence problem | Problem Set 4 (Due: Oct 22) | |
| Tue. Oct 13 | No class (fall break) | ||
| Thu. Oct 15 | Midterm exam | ||
| Tue. Oct 20 | Oracle machines, Turing reductions | ||
| Thu. Oct 22 | Kolmogorov Complexity | Problem Set 5 (Due: Nov 5) | |
| Tue. Oct 27 | Time Complexity, extended Church-Turing thesis | ||
| Thu. Oct 29 | P and NP | ||
| Tue. Nov 3 | Polynomial-time reduction, NP-completeness | ||
| Thu. Nov 5 | Cook-Levin theorem | Problem Set 6 (Due: Oct 19) | |
| Tue. Nov 10 | More NP-complete problems | ||
| Thu. Nov 12 | Space complexity, Savitch's theorem | ||
| Tue. Nov 17 | PSPACE-Completeness, TQBF | ||
| Thu. Nov 19 | More PSPACE-complete problems | Problem Set 7 (Due: Dec 3) | |
| Tue. Nov 24 | L and NL, NL-completeness | ||
| Thu. Nov 26 | No class (Thanksgiving) | ||
| Tue. Dec 1 | Immerman–Szelepcsényi theorem | ||
| Thu. Dec 3 | Special topic: Randomized computation | ||
| Tue. Dec 8 | Special topic: Interactive proofs | ||
| Thu. Dec 10 | Special topic: Circuit complexity | ||
| TBD | Final exam |