| Lecture
| Date
| Section
| Topic
|
| 1
| Wed, Aug 27
| 0.1
| Introduction
|
| 2
| Fri, Aug 29
| 0.2
| Mathematical Notions and Terminology
|
| 3
| Mon, Sep 1
| 0.3
| Definitions, Theorems, and Proofs
|
| 4
| Wed, Sep 3
| 0.4
| Types of Proof
|
| 5
| Fri, Sep 5
| 1.1
| Finite Automata - Introduction
|
| 6
| Mon, Sep 8
| 1.1
| Finite Automata - Definition and Examples
|
| 7
| Wed, Sep 10
| 1.1
| Finite Automata - Regular Operations
|
| 8
| Fri, Sep 12
| 1.2
| Nondeterminism - Introduction
|
| 9
| Mon, Sep 15
| 1.2
| Nondeterminism - Converting NFAs to DFAs
|
| 10
| Wed, Sep 17
| 1.2
| Nondeterminism - Closure Properties
|
| 11
| Fri, Sep 19
| Ex. 7.40
| Minimizing DFAs
|
| 12
| Mon, Sep 22
| 1.3
| Regular Expressions
|
| 13
| Wed, Sep 24
| 1.4
| Nonregular Languages
|
| 14
| Fri, Sep 26
| 2.1
| Context-Free Grammars - Regular Grammars
|
| 15
| Mon, Sep 29
| 2.1
| Context-Free Grammars - Derivations
|
| 16
| Wed, Oct 1
| 2.1
| Context-Free Grammars - Chomsky Normal Form
|
| 17
| Fri, Oct 3
| 2.2
| Pushdown Automata - Introduction
|
| 18
| Mon, Oct 6
| 2.2
| Pushdown Automata - Examples
|
| 19
| Wed, Oct 8
| 2.2
| Pushdown Automata - Equivalence to CFGs
|
| 20
| Fri, Oct 10
| 2.2
| Pushdown Automata - Simplifying the Grammar
|
| 21
| Wed, Oct 13
| 2.3
| Non-Context-Free Languages - The Pumping Lemma
|
| 22
| Fri, Oct 15
| 2.3
| Non-Context-Free Languages - Examples
|
| 23
| Mon, Oct 17
| 3.1
| Turing Machines - Definition and Examples
|
| 24
| Wed, Oct 22
| 3.1
| Turing Machines - More Examples
|
| 25
| Fri, Oct 24
| 3.1
| Turing Machines - Decidability
|
| 26
| Mon, Oct 27
| 3.2
| Variants of Turing Machines
|
| 27
| Wed, Oct 29
| 3.2
| Decidability and Enumerability
|
| 28
| Fri, Oct 31
| 3.2
| Closure Properties of Decidability
|
| 29
| Mon, Nov 3
| 3.3
| The Definition of Algorithm
|
| 30
| Wed, Nov 5
| 4.1
| Decidable Languages
|
| 31
| Fri, Nov 7
| 4.2
| The Halting Problem - Undecidable Languages
|
| 32
| Mon, Nov 10
| 4.2
| The Halting Problem - Undecidability
|
| 33
| Wed, Nov 12
| 5.1
| Undecidable Problems from Language Theory
|
| 34
| Fri, Nov 14
|
| No class
|
| 35
| Mon, Nov 17
| 5.3
| Mapping Reducibility
|
| 36
| Wed, Nov 19
| 7.1
| Measuring Complexity
|
| 37
| Fri, Nov 21
| 7.1
| Measuring Complexity - The TIME classes
|
| 38
| Mon, Nov 24
| 7.2
| The Class P
|
| 39
| Mon, Dec 1
| 7.3
| The Class NP
|
| 40
| Wed, Dec 3
| 7.4
| NP-Completeness
|
| 41
| Fri, Dec 5
| 7.4
| NP-Completeness
|
| 42
| Mon, Dec 8
| 7.4
| Cook's Theorem
|