Created: Wed 10 Sep 2008
Last modified:
Note: This is an approximate syllabus; it may change at any time.
- Lecture 01, Tue 01-06-2009
- Introduction; administrivia; overview of CSU390
- Reading: Sipser 0
- Lecture 02, Fri 01-09-2009
- Math primer; DFAs, state diagrams and examples
- Reading: Sipser 0, 1.1
- Lecture 03, Tue 01-13-2009
- Formal definitions; regular languages; regular operations;
regular expressions
- Reading: Sipser 1.1
- Lecture 04, Fri 01-16-2009
- Closure properties; non-determinism; equivalence of NFAs and DFAs
- Reading: Sipser 1.2
- Homework 2 assigned
- Lecture 05, Tue 01-20-2009
- Finish equivalence of NFAs and DFAs; regular expressions;
equivalence of RE and FA
- Reading: Sipser 1.3
- Lecture 06, Fri 01-23-2009
- Finish equivalence of RE and FA (NFA->RE conversion)
Existence of non-regular languages
- Reading: Sipser 1.4
- Lecture 07, Tue 01-27-2009
- Lecture 08, Fri 01-30-2009
- Context-free languages; context-free grammars; ambiguity
- Reading: Sipser 2.1-2.2
- Lecture 09, Tue 02-03-2009
- Finish ambiguity; closure properties of CFLs; decision procedures
- Reading: Sipser 2.1-2.2
- Lecture 10, Fri 02-06-2009
- Compare RLs and CFLs; pushdown automata; Equivalence of CFLs & PDAs
- Reading: Sipser 2.2
- Lecture 11, Tue 02-10-2009
- Equivalence of CFGs and PDAs
- Reading: Sipser 2.2
- Lecture 12, Fri 02-13-2009
- Pumping Lemma for CFLs
- Reading: Sipser 2.3
- Lecture 13, Tue 02-17-2009
- Lecture 14, Fri 02-20-2009
- LL parsing -- first & follow sets
- Lecture 15, Tue 02-24-2009
- Lecture 16, Fri 02-27-2009
- Midterm, Tue 03-10-2009
- Lecture 17, Fri 03-13-2009
- Turing Machines; state diagrams & examples; Church-Turing thesis
- Reading: Sipser 3.1, 3.3
- Lecture 18, Tue 03-17-2009
- Formal definitions; decidable & recognizable languages
- Reading: Sipser 3.1, 3.3
- Lecture 19, Fri 03-20-2009
- Turing Machine variants: multi-tape, non-determinisitic, etc.
- Reading: Sipser 3.2
- Lecture 20, Tue 03-24-2009
- Decidability; cardinality of infinite sets; diagonalization
- Reading: Sipser 4.1, 4.2
- Homework 06 assigned
- Lecture 21, Fri 03-27-2009
- Diagonalization; Halting Problem
- Reading: Sipser 4.2
- Lecture 22, Tue 03-31-2009
- Lecture 23, Fri 04-03-2009
- Reducibility; time complexity
- Reading: Sipser 7.1
- Lecture 24, Tue 04-07-2009
- Lecture 25, Fri 04-10-2009
- Polytime reductions
- Reading: Sipser 7.4
- Lecture 26, Tue 04-14-2009
- NP-Completeness
- Reading: Sipser 7.4-7.5
- Final Exam, Friday April 17
- 8:00-10:00 AM
- 409 Robinson Hall (RB)
Switch to:
shivers@ccs.neu.edu