| SES # | TOPICS | KEY DATES |
|---|---|---|
| Introduction and Review | ||
| L1 | Introduction | Homework 1 out |
| R1 | Math Review | |
| Finite Automata, Regular Languages, Regular Expressions | ||
| L2 | Deterministic Finite Automata (DFA) | |
| L3 | Nondeterministic Finite Automata (NFA) | Homework 1 due Homework 2 out |
| R2 | DFAs and NFAs | |
| L4 | Regular Expressions | |
| L5 | Non-Regular Languages | Homework 2 due Practice homework 2.5 out |
| R3 | Regular Expressions and Non-Regular Languages | |
| L6 | Algorithms for Automata | |
| L7 | Quiz 1 | Homework 3 out |
| R4 | Quiz Questions and Automata Wrap-up | |
| Computability Theory | ||
| L8 | Turing Machines | |
| L9 | Nondeterministic Turing Machines | Homework 3 due Homework 4 out |
| R5 | Turing Machines | |
| L10 | Undecidability | |
| L11 | PCP | Homework 4 due Homework 5 out |
| R6 | Undecidability | |
| L12 | Counter and Stack Machines | |
| L13 | Reducibility | Homework 5 due Practice homework 5.5 out |
| R7 | Counter and Stack Machines, Reducibility, Rice's Theorem | |
| L14 | Recursion Theorem | |
| L15 | Quiz 2 | Homework 6 out |
| R8 | Quiz 2 Questions and Computability Wrap-up | |
| Complexity Theory | ||
| L16 | Time Complexity | |
| L17 | Nondeterministic Time Complexity | Homework 6 due Homework 7 out |
| R9 | P and NP | |
| L18 | NP-Completeness | |
| L19 | Cook-Levin Theorem | Homework 7 due Homework 8 out |
| R10 | Poly-Time Reductions | |
| L20 | NP-Completeness II | Homework 8 due Practice homework 8.5 out |
| R11 | NP-Completeness | |
| L21 | Advanced Time Complexity | |
| L22 | Quiz 3 | Homework 9 out |
| R12 | Quiz 3 Questions and End of Time Complexity | |
| L23 | Space Complexity | |
| L24 | Space Complexity II | Homework 9 due Practice homework 10 out |
| R13 | Space Complexity III | |
| L25 | Probabilistic Complexity | |
| L26 | Probabilistic Complexity (cont.) | Practice homework 10.5 out |
| R14 | Probabilistic Complexity and Interactive Proofs | |
| Final Exam Review Session (Optional) | ||
| Final Exam | ||