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) [slides]
    Reading
    • Sipser 2.1.
    Wed, Oct 04Context-free grammars [slides]
    No reading
    Fri, Oct 06Chomsky normal form (CNF) [slides]
    No reading
    Week 7
    Mon, Oct 09Chomsky normal form (CNF) [slides]
    No reading
    Wed, Oct 11Pushdown automata (PDAs) [slides]
    Reading
    • Sipser 2.2.
    Fri, Oct 13Pushdown automata 2 [slides]
    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 23Equivalence of CFGs and PDAs [slides]
      No reading
      Wed, Oct 25Non-context-free languages and the pumping lemma [slides]
      Reading
      • Sipser 2.3.
      Fri, Oct 27TBA
      No reading
      Week 10
      Mon, Oct 30Turing machines (TMs) [slides]
      Reading
      • Sipser 3.1.
      Wed, Nov 01Turing machines (TMs) [slides]
      Reading
      • Sipser 3.2.
      Fri, Nov 03Turing machines (TMs) [slides]
      No reading
      Week 11
      Mon, Nov 06Turing machine variants [slides]
      No reading
        Wed, Nov 08Exam 2 Review [slides]
        No reading
        Fri, Nov 10Exam 2
        No reading
        Week 12
        Mon, Nov 13Church-Turing Thesis and Decidability [slides]
        Reading
        • Sipser 3.3, 4.1.
        Wed, Nov 15Decidability [slides]
        Reading
        • Sipser 4.1.
        Fri, Nov 17Decidability [slides]
        No reading
        Week 13
        Mon, Nov 20Undecidability [slides]
        Reading
        • Sipser 4.2.
        Wed, Nov 22Undecidability and reducibility [slides]
        Reading
        • Sipser 5.1.
        Fri, Nov 24No class: Thanksgiving break
        No reading
        Week 14
        Mon, Nov 27Reductions [slides]
        No reading
        Wed, Nov 29Reductions [slides]
        No reading
        Fri, Dec 01Reductions [slides]
        No reading
        Week 15
        Mon, Dec 04Mapping reducibility [slides]
        Reading
        • Sipser 5.3.
          Wed, Dec 06Mapping reductions [slides]
          No reading
          Fri, Dec 08Mapping reductions [slides]
          No reading
          Week 16
          Mon, Dec 11Final exam review
          No reading