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
Lecture 08, Mon 10-04
- Context-free languages; context-free grammars; ambiguity
- Reading: Sipser 99-106
Lecture 09, Wed 10-06
Columbus Day, Mon 10-11
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
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
Lecture 21, Mon 11-22
- P and NP, Polytime reductions
- Reading: Sipser pages 264-272
Thanksgiving Break, Wed 11-24
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
Final Exam, Wed Dec 15, 1:00 pm - 3:00 pm, Shillman Hall 135
Switch to:
viola@ccs.neu.edu