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 | Lecture 6, Problem Set 2 (Due: Sep 24) | |
| Tue. Sep 15 | Context-free languages, Pushdown automata | Lecture 7 | (Sip) 2.1, 2.2 |
| Thu. Sep 17 | Equivalence of PDA and CFG | Lecture 8 | (Sip) 2.2 |
| Tue. Sep 22 | Pumping lemma for CFL | Lecture 9 | (Sip) 2.3 |
| Thu. Sep 24 | Turing machines | Lecture 10, Problem Set 3 (Due: Oct 8) | (Sip) 3.1 |
| Tue. Sep 29 | Variants of Turing machines, Church-Turing thesis | Lecture 11 | (Sip) 3.2 |
| Thu. Oct 1 | Universal Turing machine | ||
| Tue. Oct 6 | Set cardinality, diagonalization | ||
| Thu. Oct 8 | Undecidability, halting problem | Problem Set 4 (Due: Oct 22) | |
| Tue. Oct 13 | No class (fall break) | ||
| Thu. Oct 15 | Midterm exam | ||
| Tue. Oct 20 | Mapping reductions, Rice’s theorem | ||
| Thu. Oct 22 | Post correspondence problem | Problem Set 5 (Due: Nov 5) | |
| Tue. Oct 27 | Oracle machines, Turing reductions | ||
| Thu. Oct 29 | Kolmogorov Complexity | ||
| Tue. Nov 3 | Time Complexity, time hierarchy theorem | ||
| Thu. Nov 5 | Polynomial-time reduction, NP-completeness | Problem Set 6 (Due: Oct 19) | |
| Tue. Nov 10 | Cook-Levin theorem | ||
| Thu. Nov 12 | More NP-complete problems | ||
| Tue. Nov 17 | Space complexity, Savitch's theorem | ||
| Thu. Nov 19 | PSPACE-Completeness, TQBF | Problem Set 7 (Due: Dec 3) | |
| Tue. Nov 24 | More PSPACE-complete problems | ||
| Thu. Nov 26 | No class (Thanksgiving) | ||
| Tue. Dec 1 | L and NL, NL-completeness | ||
| Thu. Dec 3 | Special topic: Randomized computation | ||
| Tue. Dec 8 | Special topic: Circuit complexity | ||
| Thu. Dec 10 | Special topic: Quantum computation | ||
| Mon. Dec 14 | Final exam, 8:00 - 10:00 AM @ BRNG B206 |