Last modified:

*Note:* This is an approximate syllabus; it may change at any time.

**Lecture 01**, Wed 01-07-04- Introduction; admistrivia; overview of CSG714
- DFAs, state diagrams and examples
- Formal definitions; regular languages; regular operations; regular expressions
*Reading:*Sipser 0, 1.1

**Lecture 02**, Wed 01-14-04- Closure properties; non-determinism; equivalence of NFAs and DFAs
- Regular expressions; equivalence of RE and FA
*Reading:*Sipser 1.2-1.3- Homework 01 assigned

**Lecture 03**, Wed 01-21-04- Finish equivalence of RE and FA
- Non-regular languages and the Pumping Lemma
- Closure properties
- Minimization of FA
*Reading:*Sipser 1.4- Homework 01 due
- Homework 02 assigned

**Lecture 04**, Wed 01-28-04- Context-free languages; context-free grammars; ambiguity
- Compare RLs and CFLs
- Pushdown automata
*Reading:*Sipser 2.1-2.2- Homework 02 due
- Homework 03 assigned

**Lecture 05**, Wed 02-04-04- Equivalence of CFLs and PDAs
- Pumping Lemma for CFLs
- Closure properties
*Reading:*Sipser 2.2-2.3- Homework 03 due
- Homework 04 assigned

**Lecture 06**, Wed 02-11-04- Turing Machines; state diagrams and examples; Church-Turing thesis
- Formal definitions; decidable and recognizable languages
*Reading:*Sipser 3.1, 3.3- Homework 04 due
- Homework 05 assigned

**Lecture 07**, Wed 02-18-04- Turing Machine variants: multi-tape and non-determinisitic
- Decidability; cardinality of infinite sets; diagonalization
*Reading:*Sipser 3.2, 4.1-4.2- Homework 05 due
*Midterm exam assigned*

**Lecture 08**, Wed 02-25-04- Halting Problem
- Reducibility
*Reading:*Sipser 4.2, 5.1*Midterm exam due*

**Lecture 09**, Wed 03-10-04- Rice's Theorem
- PCP
*Reading:*Sipser 5.2- Homework 06 assigned

**Lecture 10**, Wed 03-17-04- Time complexity
- P and NP
*Reading:*Sipser 7.1-7.3- Homework 06 due
- Homework 07 assigned

**Lecture 11**, Wed 03-24-04- Polytime reductions
- NP-Completeness
*Reading:*Sipser 7.4-7.5- Homework 07 due
- Homework 08 assigned

**Lecture 12**, Wed 03-31-04 (*Note:*Class meets in 149CN)- NP-Completeness
*Reading:*Sipser 7.4-7.5- Homework 08 due
- Homework 09 assigned

**Lecture 13**, Wed 04-07-04- Advanced topics, TBA
- Homework 09 due
- Homework 10 assigned

**Lecture 14**, Wed 04-14-04- Advanced topics, TBA
- Homework 10 due
*Final exam assigned*

- Wed 04-21-04
*Final exam due*

jaa@ccs.neu.edu