CS 383: Theory of Computation

DateTopic and readingAssignments
Week 1
Fri, Sep 01Introduction: Preliminaries [slides]
Reading
  • Sipser 0.
Week 2
Mon, Sep 04No class
No reading
Wed, Sep 06Alphabets, strings, and languages [slides]
No reading
Fri, Sep 08Deterministic finite automata (DFAs) [slides]
Reading
  • Sipser 1.1.
Week 3
Mon, Sep 11Nondeterministic finite automata (NFAs) [slides]
Reading
  • Sipser 1.2.
Wed, Sep 13Nondeterministic finite automata (NFAs) [slides]
No reading
Fri, Sep 15NFAs
No reading
Week 4
Mon, Sep 18Regular expressions (regex) [slides]
Reading
  • Sipser 1.3.
  • HW 3 two parts, download PDF from Part II
Wed, Sep 20DFAs, NFAs, and regex
No reading
Fri, Sep 22Nonregular languages and the pumping lemma [slides]
Reading
  • Sipser 1.4.
Week 5
Mon, Sep 25No class: Yom Kippur
No reading
    Wed, Sep 27Closure properties of regular languages [slides]
    No reading
    Fri, Sep 29Exam 1
    No reading
    Week 6
    Mon, Oct 02Context-free grammars (CFGs)
    Reading
    • Sipser 2.1.
    Wed, Oct 04Context-free grammars
    No reading
    Fri, Oct 06Chomsky normal form (CNF)
    No reading
    Week 7
    Mon, Oct 09Chomsky normal form (CNF)
    No reading
    • HW 5
    Wed, Oct 11Pushdown automata (PDAs)
    Reading
    • Sipser 2.2.
    Fri, Oct 13TBA
    No reading
    Week 8
    Mon, Oct 16No class: fall break
    No reading
      Wed, Oct 18No class: fall break
      No reading
      Fri, Oct 20No class: fall break
      No reading
      Week 9
      Mon, Oct 23Closure properties of context-free languages
      No reading
      • HW 6
      Wed, Oct 25Non-context-free languages and the pumping lemma
      Reading
      • Sipser 2.3.
      Fri, Oct 27TBA
      No reading
      Week 10
      Mon, Oct 30Turing machines (TMs)
      Reading
      • Sipser 3.1.
      • HW 7
      Wed, Nov 01Turing machines (TMs)
      Reading
      • Sipser 3.2.
      Fri, Nov 03TBA
      No reading
      Week 11
      Mon, Nov 06Church-Turing Thesis and Decidability
      Reading
      • Sipser 3.3, 4.1.
        Wed, Nov 08Exam 2 Review
        No reading
        Fri, Nov 10Exam 2
        No reading
        Week 12
        Mon, Nov 13Decidability
        Reading
        • Sipser 4.1.
        • HW 8
        Wed, Nov 15Undecidability
        Reading
        • Sipser 4.2.
        Fri, Nov 17TBA
        No reading
        Week 13
        Mon, Nov 20Undecidability and reducibility
        Reading
        • Sipser 5.1.
        • HW 9
        Wed, Nov 22TBA
        No reading
        Fri, Nov 24No class: Thanksgiving break
        No reading
        Week 14
        Mon, Nov 27Mapping reducibility
        Reading
        • Sipser 5.3.
        • HW 10
        Wed, Nov 29Time complexity and P
        Reading
        • Sipser 7.1, 7.2.
        Fri, Dec 01TBA
        No reading
        Week 15
        Mon, Dec 04P and NP
        Reading
        • Sipser 7.3.
        • HW 11
        Wed, Dec 06NP-completeness
        Reading
        • Sipser 7.4.
        Fri, Dec 08TBA
        No reading
        Week 16
        Mon, Dec 11Final exam review
        No reading