Tentative Schedule

Day	Topic & Slides	Chapter
Monday August 27	Introduction	0
Thursday August 30	Languages	0
Monday September 3	Finite Automacdta, Regular Languages	1
Thursday September 6	Nondeterministic Finite Automata	1
Monday September 10	Properties of Regular Languages Regular Expressions	1
Thursday September 13	Pumping Lemma for Regular Languages	1
Monday September 17	More Pumping Lemma Examples	1
Thursday September 20	Review Class for Regular Languages
Monday September24	Exam 1 Review
Thursday September 27	EXAM 1 on Regular Languages
Monday October 1	Context-Free Grammars & Languages	2
Thursday October 4	Grammar Normal Forms Compilers & Parsers	2
Tuesday October 9 (Monday Schedule)	Pushdown Automata	2
Thursday October 11	Pushdown Automata & Context-Free Lang.	2
Monday Octobe 15	Turing Machines	3
Thursday October 18	Variations of Turing Machines	3
Monday October 22	Review Class for Context-Free languages
Thursay October 25	EXAM 2 on Context-free languages
Monday October 29	Universal Turing Machine	4
Thurday November 1	Decidable Languages Chomsky's Hierarchy	4
Monday November 5	Undecidable Problems	4
Thursday November 8	Reductions for Decidability	5
Monday November 12	Post-Correspondence Problem	5
Thursday November 15	Time Complexity	7
Monday November 19	NP-Completeness – Cook’s Theorem	7
Monday November 26	NP-Complete Reductions	7
Thursday November 29	Approximation Algorithms	9
Monday December 3	Approximation Algorithms	9
Thursday December 6	Interactive Proofs and Probablistic Algorithm9	9

Extra Material

Mathematical Preliminaries

Decidable problems on Regular and Context-free languages

Grammars for regular languages

Deterministic pushdown automata (DPDA)

Properties of context-free languages

More examples of pumping lemma for context-free languages

Other models of computation