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
- Gradescope
- Blackboard
- JFLAP
- JFLAP tutorial and installation video (provided by Grant McClearn, Class of 2021; currently at Stanford)
Tentative Schedule
| Introduction | Materials |
|---|---|
| Week 1-Lecture 1 | Lecture 1 – Introduction and Overview Initial Survey |
| Finite State Automata and Pushdown Automata (Weeks 1-6) | Materials |
|---|---|
| Deterministic Finite Automata (Week 1) Chapter 1.1 (Sipser) Chapter 2 (Linz) |
Lecture 2 – Deterministic Finite Automata Lab 0 |
| Nondeterministic Finite Automata (Week 2) |
Lecture 3 – Regular Languages Lecture 4 – non-determinism Lab 1 |
| Regular Expressions (Week 3) Chapters 1.2, 1.3 (Sipser) |
Lecture 5 – NFAs and Regular Expressions Lecture 6 – Snow Day Review Lab 2 |
| Non-regular Languages (Week 4) Chapters 1.4, 2.1 (Sipser) |
Lecture 7 – Regular Language Pumping Lemma Lecture 8 – context-free grammars Lab 3 |
| Pushdown Automata and Equivalence to CFG (Week 5) Chapter 2.2 (Sipser) |
Lecture 9 – Pushdown Automata Lecture 10 – PDA, CFG, & CF-Pumping Lemma Lab 4 |
| Exam 1 (Week 6) | Tuesday lecture: Exam review |
| Computability Theory (Weeks 7-10) | Materials | |
|---|---|---|
| Turing Machines (Week 7) Chapter 3.1 (Sipser) |
Lecture 11 – Intro to Turing Machine Lecture 12 – More about Turing Machines Lab 5 |
|
| Decidable and Turing-recognizable Languages (Week 8) Chapter 4 (Sipser) |
Lecture 13 – Decidability and Recognizability Lecture 14 – More on Decidability Lab 6 |
|
| SPRING BREAK! |
||
| Reductions (Week 9) Chapter 5 (Sipser) |
Lecture 15 – Reductions Lecture 16 – More reductions Lab 7 |
|
| Exam 2 (Week 10) | Tuesday lecture: Review |
| Complexity Theory (Weeks 11-14) | Materials |
|---|---|
| Introduction to complexity theory (Week 11) Chapter 7 (Sipser) |
Lecture 17 – Complexity Lecture 18 – P and NP Lab 8 |
| NP Completeness (Week 12) |
|
| Complexity Classes (Week 13) |
|
| Review (Week 14) |
| Summary | Materials |
|---|---|
| Final Exam May 5th | Comprehensive but will focus primarily on material after Exam 2. |
Office Hours:
The instruction team’s availability for the current week is here. Any designated time slot not claimed by one-on-one meetings is open for general purpose questions from anyone in the class. All office hours will be held in the common area outside of 4000 SEH.