CS 383: Theory of Computation

DateTopic and readingAssignments
Week 1
Wed, Aug 26Introduction: Preliminaries
Reading
  • Kozen Lectures 1 and 2.
    Fri, Aug 28Alphabets, strings, and languages
    Reading
    • Kozen 2.
    Week 2
    Mon, Aug 31Deterministic finite automata (DFAs)
    Reading
    • Kozen 3, 4.
    Wed, Sep 02Automaton for multiples of 3
    Reading
    • Kozen 3, 4.
    Fri, Sep 04Closure properties 1
    Reading
    • Kozen 4.
    Week 3
    Mon, Sep 07No class: Labor Day
    No reading
    Wed, Sep 09Closure properties 2
    No reading
    Fri, Sep 11Nondeterministic finite automata (NFAs)
    Reading
    • Kozen 5.
    Week 4
    Mon, Sep 14NFAs and DFAs
    Reading
    • Kozen 6.
    Wed, Sep 16Epsilon transitions
    Reading
    • Kozen 6.
    Fri, Sep 18Nonregular languages
    Reading
    • Kozen 11.
    Week 5
    Mon, Sep 21No class: Yom Kippur
    No reading
      Wed, Sep 23The Pumping Lemma
      Reading
      • Kozen 12.
      Fri, Sep 25Regular expressions
      Reading
      • Kozen 7, 8.
      Week 6
      Mon, Sep 28Regular expressions from DFAs
      Reading
      • Kozen 9.
      Wed, Sep 30Exam 1 Review
      No reading
      Fri, Oct 02Exam 1
      No reading
      Week 7
      Mon, Oct 05Context-free grammars
      Reading
      • Kozen 19.
      Wed, Oct 07Practice with CFGs
      Reading
      • Kozen 20.
      Fri, Oct 09Chomsky normal form (CNF)
      Reading
      • Kozen 21.
      Week 8
      Mon, Oct 12Pumping lemma for CFLs
      Reading
      • Kozen 22.
        Wed, Oct 14Pumping lemma for CFLs 2
        Reading
        • Kozen 22.
        Fri, Oct 16Nondeterministic Pushdown Automata (NPDAs)
        Reading
        • Kozen 23, E.
        Week 9
        Mon, Oct 19No class: Fall Break
        No reading
        Wed, Oct 21No class: Fall Break
        No reading
        Fri, Oct 23No class: Fall Break
        No reading
        Week 10
        Mon, Oct 26Equivalence of CFGs and NPDAs
        Reading
        • Kozen 24.
          Wed, Oct 28Single-state NPDAs
          Reading
          • Kozen 25.
          Fri, Oct 30Exam 2 review
          No reading
          Week 11
          Mon, Nov 02Exam 2
          No reading
          Wed, Nov 04Turing machines (TMs)
          No reading
          Fri, Nov 06TBA
          No reading
          Week 12
          Mon, Nov 09TBA
          No reading
          Wed, Nov 11TBA
          No reading
          Fri, Nov 13TBA
          No reading
          Week 13
          Mon, Nov 16TBA
          No reading
            Wed, Nov 18TBA
            No reading
            Fri, Nov 20TBA
            No reading
            Week 14
            Mon, Nov 23TBA
            No reading
            Wed, Nov 25No class: Thanksgiving Break
            No reading
            Fri, Nov 27No class: Thanksgiving Break
            No reading
            Week 15
            Mon, Nov 30TBA
            No reading
              Wed, Dec 02TBA
              No reading
              Fri, Dec 04TBA
              No reading
              Week 16
              Mon, Dec 07TBA
              No reading
                Wed, Dec 09TBA
                No reading