|
Week |
Date |
Reading |
Topics |
|
1 |
29 Jan 2008 (Tu) |
1.2-1.4 |
Introduction and administrative trivia |
|
31 Jan 2008 (Th) |
1.4, 1.5. 2.2 |
Formal proofs; inductive proofs; central concepts of automata theory; informal picture of finite automata; deterministic finite automata |
|
|
2 |
5 Feb 2008 (Tu) |
2.3-2.4 |
Nondeterministic finite automata; an application: text search |
|
7 Feb 2008 (Th) |
2.5 |
NFA with epsilon-transitions |
|
|
3 |
12 Feb 2008 (Tu) |
3.1-3.2 |
Regular expressions, languages, and DFAs; regular expressions |
|
14 Feb 2008 (Th) |
3.3-3.4 |
Applications of regular expressions; algebraic properties of regular expressions |
|
|
4 |
19 Feb 2008 (Tu) |
Monday Schedule. No class. |
|
|
21 Feb 2008 (Th) |
4.1 |
Proving languages not to be regular; pumping lemma for regular expressions |
|
|
5 |
26 Feb 2008 (Tu) |
4.2 |
Closure properties of regular languages; decision properties of regular languages; |
|
28 Feb 2008 (Th) |
4.4 |
Equivalence and minimization of DFAs; |
|
|
6 |
4 Mar 2008 (Tu) |
Quiz 1 (everything so far) |
|
|
6 Mar 2008 (Th) |
5.1-5.2 |
Context-free grammars and languages; parse trees and ambiguity |
|
|
7 |
11 Mar 2008 (Tu) |
5.3-5.4 |
Applications of context-free grammars |
|
13 Mar 2008 (Th) |
6.1-6.2 |
Pushdown automata; the language of a PDA |
|
|
18, 20 Mar 2008 |
Spring Break. No classes. |
||
|
8 |
25 Mar 2008 (Tu) |
6.3-6.4 |
Equivalence of PDAs and CFGs; deterministic pushdown automata |
|
27 Mar 2008 (Th) |
7.1-7.2 |
Normal forms for context-free grammars; the pumping lemma for context-free languages |
|
|
9 |
1 Apr 2008 (Tu) |
7.3-7.4 |
Closure properties of context-free languages; decision properties of CFLs |
|
3 Apr 2008 (Th) |
8.1-8.2 |
Introduction to Turing machine; problems that computers cannot solve; Turing machines |
|
|
10 |
8 Apr 2008 (Tu) |
8.3-8.4 |
Programming techniques for Turing machines; extensions to the basic Turing machines |
|
10 Apr 2008 (Th) |
Quiz 2 (everything since Quiz 1) |
||
|
11 |
15 Apr 2008 (Tu) |
8.5-8.6 |
Restricted Turing machines; Turing machines and computers |
|
17 Apr 2008 (Th) |
9 |
Undecideability |
|
|
12 |
22 Apr 2008 (Tu) |
9.1-9.2 |
A language that is not recursively enumerable; an undecidable problem that is r.e. |
|
24 Apr 2008 (Th) |
9.2 |
A language that is not recursively enumerable; an undecidable problem that is r.e. |
|
|
13 |
29 Apr 2008 (Tu) |
9.3 |
Undecidable problems about Turing machines; |
|
1 May 2008 (Th) |
9.4 |
Other undecidable problems, The classes P and NP |
|
|
14 |
6 May 2008 (Tu) |
9.5 |
Rice’s theorem. |
|
8 May 2008 (Th) |
9.5 |
Post’s Correspondence Problem |
|
|
15 |
13 May 2008 (Tu) |
Review |
Review |
|
15 May 2008 (Th) |
Reading Day |
||
|
16 |
TBA |
Location TBA |
Final exam (everything) |