Prof. Tom Hayes | University at Buffalo | Fall 2026
Catalog Description: Formal models of computation and their language classes. Deterministic and non-deterministic finite automata, regular expressions, and regular languages. Context-free grammars, parse trees, and pushdown automata. Turing machines, decidability, and undecidability via diagonalization and reduction. Introduction to time complexity, P versus NP, and NP-completeness.
By the time you reach CSE 396, you've spent years learning how to build software, design efficient algorithms, and write production code. This course shifts the lens entirely. Instead of asking "How fast can I solve this problem?", we ask a much more fundamental question: "Can this problem be solved by a computer at all, and if so, what kind of machine does it require?"
By the end of the semester, you will be able to:
Primary Textbook: Michael Sipser, Introduction to the Theory of Computation (3rd Edition). Sipser's text is widely regarded as one of the clearest and most engaging introductions to the field. We will cover Chapters 0 through 5, alongside selections from Chapter 7.
This course uses a multi-tiered assessment model designed to support collaborative, AI-assisted learning while rigorously verifying individual mastery:
| Component | Weight | Description |
|---|---|---|
| TopHat Lecture Checks | 10% | Low-stakes conceptual checks during lectures to incentivize attendance and engagement (lowest 15–20% dropped). |
| In-Class Assessments | 30% | Six brief, unaided individual assessments given on Fridays to confirm mastery of techniques practiced in homework. |
| Midterm Exams | 25% | Two single-session in-class exams (12.5% each) testing conceptual synthesis and technique selection across core blocks. |
| Final Exam | 35% | Cumulative final exam, heavily weighted toward the second half of the course. |
| Homework | 0% | Formative practice sets (see policy below). |
Homework is strictly formative. Its sole purpose is to prepare you for the in-class assessments and exams. You are explicitly encouraged to use textbooks, lecture notes, peers, and AI tools (such as ChatGPT) to work through problems, understand tricky constructions, and debug proofs. Detailed solutions will be released following each cycle. Because homework is practice rather than evaluation, it carries no direct grade weight; your mastery is demonstrated independently during the in-class assessments.
Final letter grades are calculated based on your accumulated weighted score across all components, using standard university grading cutoffs with appropriate rounding:
We live in a world with powerful AI tools, and I have no interest in pretending they don't exist. On your formative homework, you are explicitly encouraged to use textbooks, classmates, and AI tools like ChatGPT. Use them as sounding boards, syntax checkers, or tutors to help you understand why a DFA construction works or how a proof structure hangs together.
However, keep in mind the reality of learning: an AI can write a proof for you, but it cannot build your intuition. When you walk into an in-class assessment or an exam, you will be on your own. Use the homework to learn deeply so that you can perform confidently when it counts.
Theory is hard to absorb purely from static notes. Lectures are where we unpack the intuition behind heavy proofs and build constructions live. Furthermore, our Monday morning tutorial is designed as an active problem-solving workshop—a low-stress space to wrestle with concepts before they hit the assessments. While attendance isn't exhaustively tracked outside of TopHat checks, showing up consistently is the single best predictor of success in this course.
Life happens—illnesses occur, personal emergencies arise, and unexpected conflicts pop up. Because our in-class assessments are frequent (six total), a single missed check won't sink your grade. If you face a significant, documented emergency that keeps you away for an extended period, reach out to me as soon as possible so we can find a fair path forward.
I trust you, and I want an environment where we respect each other's work. Collaboration and external resources are wonderful for learning during homework cycles. But in-class assessments, midterms, and the final exam are strictly individual and unaided. Bringing unauthorized notes, communication devices, or AI tools into an exam environment is a serious violation of university policy and breaks the trust that makes this course structure work. Let's keep things honest and fair for everyone.
Your well-being matters far more than any single grade. If you have a registered disability that requires accommodations, please connect with the Office of Accessibility Resources (OAR) early in the semester so we can get your plan in place. More broadly, if you are hitting a wall—academically, personally, or emotionally—please don't ghost the course. Reach out to me, or take advantage of UB's campus counseling and support resources. We can almost always find a way to navigate a tough spot if we talk about it early.