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