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 18Equivalence of CFGs and PDAs [slides]
        No reading
          Wed, Mar 20Non-context-free languages and the pumping lemma [slides]
          Reading
          • Sipser 2.3.
          Fri, Mar 22TBA
          No reading
          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 08Turing machine variants [slides]
              No reading
                Wed, Apr 10Exam 2 Review [slides]
                No reading
                Fri, Apr 12Exam 2
                No reading
                Week 11
                Mon, Apr 15Church-Turing Thesis and Decidability [slides]
                Reading
                • Sipser 3.3, 4.1.
                  Wed, Apr 17Decidability [slides]
                  Reading
                  • Sipser 4.1.
                  Fri, Apr 19Decidability [slides]
                  No reading
                  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