Syllabus

Week 1: 1/10
        Mathematical Foundations
        Sipser: Chapter 0
        Finite automata
        Sipser: Section 1.1
  

Week 2: 1/17
        Finite automata; Regular languages
        Sipser: Sections 1.1, 1.2, 1.3
  

Week 3: 1/24
        Non-determinism; Non-regular languages; Pumping lemma
        Sipser: Sections 1.3, 1.4
  

Week 4: 1/31
        Context-free languages: Context-free grammars
        Sipser: Section 2.1, 2.2
  

Week 5: 2/7
        Applications; Review
        Sipser: Chapter 1
        Quiz 1
  

Week 6: 2/14
        Context-free languages: Pushdown automata, Non-context-free grammars
        Sipser: Section 2.2, 2.3
        Deterministic context-free languages
        Sipser: Section 2.5
  

Week 7: 2/21
        Deterministic context-free languages
        Sipser: Section 2.5
        Church-Turing thesis: Turing Machines
        Sipser: Sections 3.1, 3.2
  

Week 8: 2/28
        Church-Turing thesis: Variants of Turing Machines; Algorithm
        Sipser: Sections 3.2, 3.3
        Decidability: decidable languages
        Sipser: Section 4.1
  

Week 9: 3/14
        Review
        Quiz 2
  

Week 10: 3/21
        The Halting problem
        Sipser: Section 4.2
        Reducibility
        Sipser: Sections 5.1, 5.3
  

Week 11: 3/28
        Complexity theory: Time complexity
        Sipser: Section 7.1
        Complexity theory: The class P, the class NP
        Sipser: Section 7.2, 7.3
  

Week 12: 4/4
        Complexity theory: The class P, the class NP
        Sipser: Section 7.2, 7.3
        Complexity theory: NP-completeness
        Sipser: Section 7.4
  

Week 13: 4/11
        NP-completeness, some NP-complete problems
        Sipser: Section 7.4, 7.5
  

Week 14: Finals week
        Quiz 4: time and room TBA