Instructor: Binghui Peng
Email: binghuip@umd.edu
Instructor Office Hours: Thursday 10:00am -- 11:00am, IRB 5130
Teaching Assistant: Mattias Ehatamm
Email: mehatamm@umd.edu
TA Office Hours: Tuesday 2:00 pm -- 3:00 pm, AVW 4160
piazza: https://piazza.com/umd/spring2026/cmsc452
syllabus: pdf
midterm: March 24th, in class exam
Introduction to the theory of computation. Topics include regular languages, finite automata, context-free languages, Turing machines, decidability, and an introduction to computational complexity
| Lecture | Topic | Slides | Supplementary reading |
|---|---|---|---|
| Feb. 3 | Introduction, DFA | intro dfa | |
| Feb. 5 | DFA closure, DFA for arithmic modular | dfa-closure | |
| Feb. 10 | NFA | nfa | |
| Feb. 12 | NFA equivalence, NFA closure | nfa-equiv | |
| Feb. 17 | NFA with small states | DFA/NFA states | |
| Feb. 19 | Pumping Lemma | pumping-lemma1 | |
| Feb. 24 | Pumping Lemma (continued) | pumping-lemma2 | Section 1.4 of Sipser's Book |
| Feb. 26 | Regular expression | regex | REU program |
| March. 3 | Context free language | cfl | Section 2.2, 2.3 of Sipser's Book |
| March. 5 | CYK algorithm | cyk |
Last updated: Spring 2026