Created: Fri 10 Sep 2004
Last modified:
Note: This is an approximate syllabus; it may change at any time.
- Lecture 01, Fri 09-10-04
- Introduction; admistrivia; overview of CSU390
- Reading: Sipser 0
- Lecture 02, Tue 09-14-04
- Math primer; DFAs, state diagrams and examples
- Reading: Sipser 0, 1.1
- Homework 01 assigned
- Lecture 03, Fri 09-17-04
- Formal definitions; regular languages; regular operations; regular expressions
- Reading: Sipser 1.1
- Lecture 04, Tue 09-21-04
- Closure properties; non-determinism; equivalence of NFAs and DFAs
- Reading: Sipser 1.2
- Homework 01 due
- Homework 02 assigned
- Lecture 05, Fri 09-24-04
- Finish equivalence of NFAs and DFAs; regular expressions; equivalence of RE and FA
- Reading: Sipser 1.3
- Lecture 06, Tue 09-28-04
- Finish equivalence of RE and FA;
non-regular languages and the Pumping Lemma
- Reading: Sipser 1.4
- Homework 02 due
- Homework 03 assigned
- Lecture 07, Fri 10-01-04
- The Pumping Lemma; closure properties; minimization of FA
- Handouts:
- Reading: Sipser 1.4
- Lecture 08, Tue 10-05-04
- Context-free languages; context-free grammars; ambiguity
- Reading: Sipser 2.1-2.2
- Handouts:
- Homework 03 due
- Homework 04 assigned
- Lecture 09, Fri 10-08-04
- Finish ambiguity; compare RLs and CFLs; pushdown automata
- Reading: Sipser 2.1-2.2
- Lecture 10, Tue 10-12-04
- Lecture 11, Fri 10-15-04
- Pumping Lemma for CFLs; closure properties
- Handouts:
- Reading: Sipser 2.3
- Lecture 12, Tue 10-19-04
- Turing Machines; state diagrams and examples; Church-Turing thesis
- Reading: Sipser 3.1, 3.3
- Lecture 13, Fri 10-22-04
- Formal definitions; decidable and recognizable languages
- Reading: Sipser 3.1, 3.3
- Homework 05 due
- Note: This assignment cannot be handed in late.
I will be passing out solutions to this assignment the day
it is due, in preparation for the midterm exam.
- Lecture 14, Tue 10-26-04
- Lecture 15, Fri 10-29-04
- Turing Machine variants: multi-tape and non-determinisitic
- Reading: Sipser 3.2
- Lecture 16, Tue 11-02-04
- Decidability; cardinality of infinite sets; diagonalization
- Reading: Sipser 4.1, 4.2
- Homework 06 assigned
- Lecture 17, Fri 11-05-04
- Diagonalization; Halting Problem
- Reading: Sipser 4.2
- Lecture 18, Tue 11-09-04
- Lecture 19, Fri 11-12-04
- Redicibility; time complexity
- Reading: Sipser 7.1
- Lecture 20, Tue 11-16-04
- Lecture 21, Fri 11-19-04
- Polytime reductions
- Reading: Sipser 7.4
- Lecture 22, Tue 11-23-04
- NP-Completeness
- Reading: Sipser 7.4-7.5
- Homework 08 due
- Lecture 23, Tue 11-30-04
- NP-Completeness
- Reading: Sipser 7.4-7.5
- Homework 09 assigned
- Lecture 24, Fri 12-03-04
- NP-Completeness
- Reading: Sipser 7.4-7.5
- Lecture 25, Tue 12-07-04
- NP-Completeness
- Reading: Sipser 7.4-7.5
- Homework 09 due
Switch to:
jaa@ccs.neu.edu