This is a core undergraduate Computer Science course on the theory of computing. The course introduces the foundations of computer computer science including questions such as “what is computation”, “what are the mathematical models of computing machines”, “what is a computable problem”, and “what is efficiently computable”. The course covers these questions and in the process introduces important concepts such as Turing machines, formal languages, models of automata, and an introduction to complexity theory. This is a theoretical course and requires rigorous mathematical analysis, including deriving formal proofs, which will help you develop your on mathematical abstraction and problem solving skills. The lecture, and some lab sessions, will consist of in-class activities and students will be required to work in groups.
Announcements
- This website is permanently under construction - all content subject to change!
Class Resources
- Piazza
- Blackboard
- Gradescope
- JFLAP
- JFLAP tutorial and installation video (provided by Grant McClearn, Class of 2021; currently at Stanford)
Tentative Schedule
| Introduction | Materials |
|---|---|
| Week 1-Lecture 0 | Course Introduction |
| Finite State Automata and Pushdown Automata (Weeks 1-6) | Materials |
|---|---|
| Deterministic Finite Automata (Week 1) Chapter 1.1 (Sipser) Chapter 2 (Linz) |
Lecture 1 – Introduction to Finite Automata Lecture 2 – Building Finite Automata Lab 1 – Review: Proof techniques, Languages, Graphs Quiz 1 |
| Nondeterministic Finite Automata (Week 2) |
Lecture 3 – Regular Languages and NFAs Lecture 4 – NFA==DFA and Regular Language Properties using NFAs Lab 2 Quiz 2 |
| Regular Expressions and Non-regular Languages (Week 3) |
Lecture 5 – Regular Expressions and equivalence to NFAs Lecture 6 – Regular Language Pumping Lemma Lab 3 Quiz 3 |
| Non-regular Languages and Pushdown Automata (Week 4) |
Lecture 7 – Proving Non-Regularity Lecture 8 – Pushdown Automata Lab 4 |
| Context-Free Grammars and Equivalence to PDAs (Week 5) |
Lecture 9 – Context Free Grammars Lecture 10 – PDA==CFG and CFG Pumping Lemma Lab 5 |
Exam 1 (Week 6) Feb. 22 |
Lecture 11 – Exam 1 Review All material on automata and languages they recognize. |
| Computability Theory (Weeks 7-10) | Materials |
|---|---|
| Turing Machines (Week 7) |
Lecture 12 – Introduction to Turing Machines Lecture 13 – More Turing Machines and Variants Lab 6 |
| Decidable and Turing-recognizable Languages (Week 8) |
Lecture 14 – Decidable Languages about Machines Lecture 15 – An Undecidable Language Lab 7 |
| Reductions (Week 9) |
Lecture 16 – Reductions Lecture 17 – Reduction Types and Kolmogorov Complexity Lab 8 |
| Exam 2 (Week 10) Mar. 28 | Lecture 18 – Exam 2 Review All material on Turing machines and computability |
| Complexity Theory (Weeks 11-14) | Materials |
|---|---|
| P and NP (Week 11) |
Lecture 19 – Polynomial Time Computation Lab 9 Lecture 20 – The Class NP Quiz |
| NP Completeness (Week 12) |
Lecture 21 – NP Completeness Lecture 22 – More NP Complete Problems Lab 10 |
| Complexity Classes and Interactive Proofs (Week 13) |
Lecture 23 – P, NP, and co-NP Lecture 24 – Interactive Proofs Lab 11 |
| Zero-Knowledge Proofs and Review (Week 14) |
Lecture 25 – Zero-Knowledge Proofs Lecture 26 – Exam 3 Review |
| Summary | Materials |
|---|---|
| Final Exam DATE AND TIME TBD | Comprehensive but will focus primarily on material after Exam 2. |
Office Hours
| Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|
| 4:00-6:00 – Suvasree | 12:45-2:30 – Ozzy 2:30-3:30 – Arkady 4:45-5:30 – Ethan |
3:30-6:00 – Ethan 6:00-7:00 – Ozzy |
10:00-11:00 – Arkady 1:30-2:30 – Arkady |
All office hours will be held in the common area on the 4th floor of SEH.