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

**Lecture 01**, Wed 09-08

- Introduction; admistrivia; overview of CS3800; math primer.
*Reading:*Sipser 0

**Lecture 02**, Mon 09-13

- Finish math primer; DFAs, state diagrams and examples; formal definition of regular languages.
*Reading:*Sipser 0; 1.1 pages 31-43

**Lecture 03**, Wed 09-15

- Regular operations; mention of regular expressions; closure properties; non-determinism;
*Reading:*Sipser pages 44-51- Homework 01 assigned

**Lecture 04**, Mon 09-20

- Non-determinism; equivalence of NFAs and DFAs; closure properties
*Reading:*Sipser pages 52-60

**Lecture 05**, Wed 09-22

- finish closure properties; regular expressions; equivalence of RE and FA
*Reading:*Sipser pages 61-69- Homework 01 due
- Homework 02 assigned

**Lecture 06**, Mon 09-27

- Finish equivalence of RE and FA.
*Reading:*Sipser pages 70-75

**Lecture 07**, Wed 09-29

- Non-regular languages and the Pumping Lemma
*Reading:*Sipser 76-82- Homework 02 due
- Homework 03 assigned

**Lecture 08**, Mon 10-04

- Context-free languages; context-free grammars; ambiguity
*Reading:*Sipser 99-106

**Lecture 09**, Wed 10-06

- Pushdown automata; Equivalence of CFLs and PDAs
*Reading:*Sipser 109-118- Homework 03 due
- Homework 04 assigned

**Columbus Day**, Mon 10-11

*No class...*

**Lecture 10**, Wed 10-13

- Finish equivalence of CFLs and PDAs; Pumping Lemma for CFLs, examples.
*Reading:*Sipser 119-127- Sample mid-term handed out, make sure to get a copy.
- Homework 04 due
- Homework 05 assigned 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 11**, Mon 10-18

- Pumping Lemma for CFLs, proof; closure properties; Turing Machines;
*Reading:*Sipser 123-127, 138-139

**Lecture 12**, Wed 10-20

- Turing Machines; state diagrams and examples;
*Reading:*Sipser 140-147- 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 13**, Mon 10-25

*Midterm exam*(in class)

**Lecture 14**, Wed 10-27

- Turing Machine variants: multi-tape and non-determinisitic;
*Reading:*Sipser 148-154

**Lecture 15**, Mon 11-01

- Church-Turing thesis; Decidability;
*Reading:*Sipser 154-170

**Lecture 16**, Wed 11-03

- Decidability; cardinality of infinite sets; diagonalization
*Reading:*Sipser 171-177- Homework 06 assigned

**Lecture 17**, Mon 11-8

- Undecidability; Halting Problem
*Reading:*Sipser 178-182; 187-190

**Lecture 18**, Wed 11-10

- Rice's theorem; Kolmogorov complexity
*Reading:*Sipser Problem 5.28, pages 234-235, Definition 6.23, Page 239- Homework 06 due
- Homework 07 assigned

**Lecture 19**, Mon 11-15

- Undecidability of logical theories; Time complexity
*Reading:*Sipser page 224, Theorem 6.13, pages 247-253

**Lecture 20**, Wed 11-17

- P and NP
*Reading:*Sipser pages 254-261- Homework 07 due
- Homework 08 assigned

**Lecture 21**, Mon 11-22

- P and NP, Polytime reductions
*Reading:*Sipser pages 264-272

**Thanksgiving Break**, Wed 11-24

*No class...*

**Lecture 22**, Mon 11-29

- NP-Completeness
*Reading:*Sipser 273-276

**Lecture 23**, Wed 12-01

- NP-Completeness
*Reading:*Sipser Theorem 7.44, 7.56, and sketch of 7.46- Homework 08 due
- Homework 09 assigned. 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 final exam.

**Lecture 24**, Mon 12-06

- The Cook-Levin Theorem
*Reading:*Sipser 276-283

**Lecture 25**, Wed 12-8

- A glimpse beyond
- Homework 09 due

**Final Exam**, Wed Dec 15, 1:00 pm - 3:00 pm, Shillman Hall 135

viola@ccs.neu.edu