CS 383: Theory of Computation

DateTopic and readingAssignments
Week 1
Mon, Feb 05Introduction: Preliminaries [slides]
Reading
  • Sipser 0.
    Wed, Feb 07Alphabets, strings, and languages [slides]
    No reading
    Fri, Feb 09Deterministic finite automata (DFAs) [slides]
    Reading
    • Sipser 1.1.
    Week 2
    Mon, Feb 12Nondeterministic finite automata (NFAs) [slides]
    Reading
    • Sipser 1.2.
    Wed, Feb 14Nondeterministic finite automata (NFAs) [slides]
    No reading
    Fri, Feb 16NFAs
    No reading
    Week 3
    Mon, Feb 19Regular expressions (regex) [slides]
    Reading
    • Sipser 1.3.
    Wed, Feb 21DFAs, NFAs, and regex
    No reading
    Fri, Feb 23Nonregular languages and the pumping lemma [slides]
    Reading
    • Sipser 1.4.
    Week 4
    Mon, Feb 26Closure properties of regular languages [slides]
    No reading
    • HW 3 two parts, download PDF from Part II
    Wed, Feb 28TBA
    No reading
    Fri, Mar 01Exam 1
    No reading
    Week 5
    Mon, Mar 04Context-free grammars (CFGs) [slides]
    Reading
    • Sipser 2.1.
      Wed, Mar 06Context-free grammars [slides]
      No reading
      Fri, Mar 08Chomsky normal form (CNF) [slides]
      No reading
      Week 6
      Mon, Mar 11Chomsky normal form (CNF) [slides]
      No reading
      Wed, Mar 13Pushdown automata (PDAs) [slides]
      Reading
      • Sipser 2.2.
      Fri, Mar 15Pushdown automata 2 [slides]
      No reading
      Week 7
      Mon, Mar 18Building PDAs
      No reading
      Wed, Mar 20Equivalence of CFGs and PDAs [slides]
      No reading
      Fri, Mar 22Non-context-free languages and the pumping lemma [slides]
      Reading
      • Sipser 2.3.
      Week 8
      Mon, Mar 25No class: spring break
      No reading
        Wed, Mar 27No class: spring break
        No reading
        Fri, Mar 29No class: spring break
        No reading
        Week 9
        Mon, Apr 01Turing machines (TMs) [slides]
        Reading
        • Sipser 3.1.
        Wed, Apr 03Turing machines (TMs) [slides]
        Reading
        • Sipser 3.2.
        Fri, Apr 05Turing machines (TMs) [slides]
        No reading
        Week 10
        Mon, Apr 08Homework work/exam study day: No instruction
        No reading
          Wed, Apr 10Exam 2 review [slides]
          No reading
          Fri, Apr 12Exam 2
          No reading
          Week 11
          Mon, Apr 15Turing machine variants [slides]
          No reading
          Wed, Apr 17Church-Turing Thesis and Decidability [slides]
          Reading
          • Sipser 3.3, 4.1.
          Fri, Apr 19Decidability [slides]
          Reading
          • Sipser 4.1.
          Week 12
          Mon, Apr 22Undecidability [slides]
          Reading
          • Sipser 4.2.
          Wed, Apr 24Undecidability and reducibility [slides]
          Reading
          • Sipser 5.1.
          Fri, Apr 26Reductions [slides]
          No reading
          Week 13
          Mon, Apr 29Reductions [slides]
          No reading
            Wed, May 01Reductions [slides]
            No reading
            Fri, May 03Mapping reducibility [slides]
            Reading
            • Sipser 5.3.
            Week 14
            Mon, May 06Mapping reductions [slides]
            No reading
            Wed, May 08Mapping reductions [slides]
            No reading
            Fri, May 10Final exam review
            No reading