Lecture 
Date 
Section/Pages 
Topic 
Introduction to the Theory of Computation 
1 
Wed, Aug 24 

Introduction 
2 
Fri, Aug 26 
1.1 
Mathematical Preliminaries 
3 
Mon, Aug 29 
1.2 
Languages and Grammars 
Finite Automata 
4 
Wed, Aug 31 
2.1 
Deterministic Finite Automata 
5 
Fri, Sep 2 
2.1 
DFA Examples 
6 
Mon, Sep 5 
2.2 
Nondeterministic Finite Automata 
7 
Wed, Sep 7 
2.3 
Converting NFAs to DFAs 
8 
Fri, Sep 9 
2.3 
NFAs to DFAs Examples 
9 
Mon, Sep 12 
2.4 
Minimizing DFAs 
Regular Languages and Regular Grammars 
10 
Wed, Sep 14 
3.1 
Regular Expressions 
11 
Fri, Sep 16 
3.2 
Regular Expressions and DFAs 
12 
Mon, Sep 19 
3.3 
Regular Grammars 
Properties of Regular Languages 
13 
Wed, Sep 21 
4.1 
Closure Properties of Regular Languages 
Fri, Sep 23 
Test 1 
14 
Mon, Sep 26 
4.2 
Decision Problems for Regular Languages 
15 
Wed, Sep 28 
4.3 
Nonregular Languages 
ContextFree Languages 
16 
Fri, Sep 30 
5.1  5.2 
ContextFree Grammars 
Simplification of Grammars and Normal Forms 
17 
Mon, Oct 3 
6.1 
Transforming Grammars 
18 
Wed, Oct 5 
6.2 
Chomsky Normal Form 
19 
Fri, Oct 7 
6.3 
The CYK Parsing Algorithm 
20 
Mon, Oct 10 
 
Pushdown Automata 
21 
Wed, Oct 12 
7.1 
Pushdown Automata 
22 
Fri, Oct 14 
7.2 
Equivalence of CFGs and PDAs (Part 1) 
Mon, Oct 17 
Fall Break 
23 
Wed, Oct 19 
7.2 
Equivalence of CFGs and PDAs (Part 2) 
Fri, Oct 21 
Test 2 
Properties of ContextFree Languages 
24 
Mon, Oct 24 
8.1  8.2 
Properties of ContextFree Languages 
Turing Machines 
25 
Wed, Oct 26 
9.1 
Turing Machines 
26 
Fri, Oct 28 
9.2 
Turing Machines Examples 
27 
Mon, Oct 31 
9.2 
More Turing Machine Examples 
Other Models of Turing Machines 
28 
Wed, Nov 2 
10.1  10.2 
Enhanced Turing Machines 
29 
Fri, Nov 4 
10.2 
Nondeterministic Turing Machines 
30 
Mon, Nov 7 
10.3 
Universal Turing Machines 
A Hierarchy of Formal Languages 
31 
Wed, Nov 9 
11.1 
Recursive Languages 
32 
Fri, Nov 11 
11.1 
Enumerability

Limits of Algorithmic Computation 
33 
Mon, Nov 14 
12.1 
The Halting Problem 
34 
Wed, Nov 16 
12.2 
Decidability 
Fri, Nov 18
 Test 3 
An Overview of Computational Complexity 
35 
Mon, Nov 21 
14.1  14.2 
Complexity

Wed, Nov 23 
Thanksgiving Break 
Fri, Nov 25 
Thanksgiving Break 
36 
Mon, Nov 28 
14.3  14.5 
The Classes P and NP 
37 
Wed, Nov 30 
14.5 
Nondeterministic Programming in C 
38 
Fri, Dec 2 
14.6 
PolynomialTime Reductions 
39 
Mon, Dec 5 
14.7 
NPCompleteness 
Fri, Dec 9
 Final Exam (2:00  5:00)
