CS154: Introduction to the Theory of Computation

General Information

Instructors: Omer Reingold and Li-Yang Tan
CAs: Addison Prairie (aprairie@stanford.edu)
        Freya Edholm (fedholm@stanford.edu)
Time: Tuesdays and Thursdays, 10:30-11:50am

Addy's OH: Mondays and Fridays, 4-5pm, CoDa B43
Freya's OH: Thursday, 3:30-5:30pm, Huang basement
Omer's and Li-Yang's OH: After class by appointment

Textbook and Resources

Introduction to the Theory of Computation, by Michael Sipser
CS154 lecture videos, by Omer Reingold
CS154 lecture slides, by Omer Reingold

List of Topics

  • Automata Theory
    DFAs, NFAs, and regular languages
    Pumping lemma
    Myhill-Nerode theorem
    DFA minimization
    Streaming and communication complexity
  • Computability Theory
    Turing machines
    Unrecognizability and undecidability
    Reductions
    Rice's theorem
    Logic and Kolmogorov complexity
  • Complexity Theory
    Time complexity
    NP and polynomial-time reductions
    NP-completeness and Cook-Levin
    coNP and the polynomial hierarchy
    Space complexity, interactive proofs, and randomness

Lecture schedule

(Will be updated as the quarter progresses. Supplementary material listed in gray.)
  • Lecture 1: Course overview
  • Lecture 2: DFAs, closure properties, nondeterminism
    Chapters 1.1-1.2 of Sipser
    Videos 6, 7, 8
  • Lecture 3: Equivalence between DFAs and NFAs; Regular expressions
    Chapters 1.2-1.3 of Sipser
    Videos 9, 10, 11
  • Lecture 4: Pumping lemma and DFA minimization
    Chapter 1.4 of Sipser
    Videos 12, 13
  • Lecture 5: Myhill-Nerode and Streaming
    Videos 14 and 16
  • Lecture 6: Streaming continued
    Video 16
  • Lecture 7: Communication complexity
    Video 17
  • Lecture 8: Turing machines
    Chapter 3 of Sipser
    Video 18-21
  • Lecture 9: Unrecognizability and undecidability
    Chapters 4 and 5 of Sipser
    Videos 22-24
  • Lecture 10: Mapping reductions
    Chapters 4 and 5 of Sipser
    Videos 22-24
  • Lecture 11: In-class midterm
  • Lecture 12: Rice's Theorem
    Chapter 5 of Sipser
    Video 25
  • Lecture 13: Oracle reductions and Self-reference
    Chapters 6.1 and 6.3 of Sipser
    Videos 26 and 27
  • Lecture 14: Kolmogorov complexity and Time Complexity
    Chapters 6.4, 7.1, and 7.2 of Sipser
    Videos 29, 30, 31
  • Lecture 15: NP and polynomial-time reductions
    Chapter 7.3 of Sipser
    Videos 32 and 33
  • Lecture 16: Cook-Levin
    Chapter 7.4 of Sipser
    Video 34
  • Lecture 17: Cook-Levin continued
    Chapter 7.4 of Sipser
    Video 34
  • Lecture 18: More NP-completeness
    Chapter 7.5 of Sipser
    Video 35
  • Lecture 19: coNP and the polynomial hierarchy
    Chapter 10.3 of Sipser
    Videos 36 and 37
  • Lecture 20: Space complexity and final review
    Chapter 8 of Sipser
    Video 38

Evaluation

(Tentative; subject to change.)
•  7 problem sets (50%, weighted by total score per set)
•  Midterm (20%)
•  Final (30%)
•  CR: ≥ 70%
Policies:
•  Groups of ≤ 3 for each pset
•  4 late days, ≤ 2 per pset
   •  Each late day counts towards each group member's quota.
   •  Late days are not transferable.
•  Regrade requests must be submitted within 1 week

Coursework schedule

(Tentative; subject to change.)
•  Pset 1 due: Tues of Week 3 (Oct 6), 10:30am
•  Pset 2 due: Tues of Week 4 (Oct 13), 10:30am
•  Pset 3 due: Tues of Week 5 (Oct 20), 10:30am
•  Midterm: Tues of Week 6 (Oct 27), 10:30am-11:50am
•  Pset 4 due: Wed of Week 7 (Nov 4), 10:30am
•  Pset 5 due: Tues of Week 8 (Nov 10), 10:30am
•  Pset 6 due: Tues of Week 9 (Nov 17), 10:30am
•  Pset 7 due: Tues of Week 10 (Dec 1), 10:30am