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 | 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 – Finite Automata Lecture 2 – Building DFAs Quiz 1 Review of Proof Techniques |
| Nondeterministic Finite Automata (Week 2) |
Lecture 3 – Regular Languages and Nondeterminism Lecture 4 – NFA==DFA Lab 1 Quiz 2 |
| Regular Expressions and Non-regular Languages (Week 3) |
Lecture 5 – NFAs and Regular Expressions Lecture 6 – Regular Language Pumping Lemma Lab 2 Quiz 3 |
| Non-regular Languages and Pushdown Automata (Week 4) |
Lecture 7 – Proving Languages Not Regular Lecture 8 – PDAs Hackathon Lab 3 |
| Context-Free Grammars and Equivalence to PDAs (Week 5) |
Lecture 9 – Context Free Grammars Lecture 10 – CFG=PDA Lab 4 |
Exam 1 (Week 6) Feb. 20 |
All material on finite automata Lecture 11 – Exam review |
| Computability Theory (Weeks 7-10) | Materials |
|---|---|
| Turing Machines (Week 7) |
Lecture 12 – Turing Machines Lecture 13 – More Turing Machines Lab 5 Quiz 4 |
| Decidable and Turing-recognizable Languages (Week 8) |
Lecture 14 – Decidable and Turing Recognizable Languages Lecture 15 – An Undecidable Language Lab 6 |
| Reductions (Week 9) |
Lecture 16 – Proofs by Reduction Lecture 17 – Reductions and Kolmogorov Complexity Lab 7 |
| Exam 2 (Week 10) Mar. 27 | All material on Turing machines and computability Lecture 18 – Exam review |
| Complexity Theory (Weeks 11-14) | Materials |
|---|---|
| P and NP (Week 11) |
Lecture 19 – P Lecture 20 – NP Quiz 5 Lab 9 |
| NP Completeness (Week 12) |
Lecture 21 – NP-Completeness Lecture 22 – More NP-Completeness Lab 10 |
| Complexity Classes and Interactive Proofs (Week 13) |
Lecture 23 – Ladner’s Theorem and co-NP Lecture 24 – Interactive Proofs Lab 11 |
| Zero-Knowledge Proofs and Review (Week 14) |
Lecture 25 – ZK Proofs Lecture 26 – Exam Review |
| Summary | Materials |
|---|---|
| Final Exam TBD | Comprehensive but will focus primarily on material after Exam 2. |
Office Hours:
| Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|
| 2:10-3:10 – Freya | 10:00-11:00 – Arkady 1:30-3:30 – Freya 5:00-6:00 – Jie |
3:30-5:00 – Ozzy 5:00-6:00 – Jie 6:00-8:00 – Suvasree |
1:00-3:00 – Laura | 10:30-12:00 – Ozzy 12:00-1:00 – Arkady |
All office hours will be held in the common area on the 4th floor of SEH.