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 |
| Nondeterministic Finite Automata (Week 2) |
|
| Regular Expressions and Non-regular Languages (Week 3) |
|
| Non-regular Languages and Pushdown Automata (Week 4) |
|
| Context-Free Grammars and Equivalence to PDAs (Week 5) |
|
Exam 1 (Week 6) Feb. 20 |
All material on finite automata |
| Computability Theory (Weeks 7-10) | Materials |
|---|---|
| Turing Machines (Week 7) |
|
| Decidable and Turing-recognizable Languages (Week 8) |
|
| Reductions (Week 9) |
|
| Exam 2 (Week 10) Mar. 27 | All material on Turing machines and computability |
| Complexity Theory (Weeks 11-14) | Materials |
|---|---|
| P and NP (Week 11) |
|
| NP Completeness (Week 12) |
|
| Complexity Classes and Interactive Proofs (Week 13) |
|
| Zero-Knowledge Proofs and Review (Week 14) |
| Summary | Materials |
|---|---|
| Final Exam TBD | Comprehensive but will focus primarily on material after Exam 2. |
Office Hours:
All office hours will be held in the common area on the 4th floor of SEH.