Topics	Slides per page
Introduction	1(pdf) 2(pdf)
Finite Automata	1(pdf) 2(pdf)
Finite Automata (cont.)	1(pdf) 2(pdf)
Application of FA's (by --)
Regular Languages	1(pdf) 2(pdf)
Non-Regular Languages	1(pdf) 2(pdf)
Application of Regular Expressions (by --)
Context-Free Grammars	1(pdf) 2(pdf)
Pushdown Automata	1(pdf) 2(pdf)
Non-Context-Free Languages	1(pdf) 2(pdf)
Application of Context-Free Grammars (by --)
Turing Machines	1(pdf) 2(pdf)
Variants of Turing Machine	1(pdf) 2(pdf)
PDA with the ability to flip its stacks (by --)	(paper)
Markup Languages & XML (by --)
Algorithms and Turing Machines	1(pdf) 2(pdf)
Decidable Languages	1(pdf) 2(pdf)
Turing Machines and Computers (by --)
Undecidable Languages	1(pdf) 2(pdf)
Reducibility	1(pdf) 2(pdf)
Post's Correspondence Problem is Undecidable (by --)
Time Complexity	1(pdf) 2(pdf)
Complexity Classes P and NP	1(pdf) 2(pdf)
NP-completeness; The Cook-Levin Theorem	1(pdf) 2(pdf)
More NP-complete Problems (by --)

Office hours: TR 2:00 - 3:30 pm or by appointment

Textbooks:


John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman,	Michael Sipser,	Christos H. Papadimitriou,
Introduction to Automata Theory, Languages, and Computation, 2/e.	Introduction to the Theory of Computation,	Computational Complexity,
Addison-Wesley, 2001.	PWS Publishing, Boston 1997.	Addison-Wesley, 1994.

HOMEWORKS

Extra Credit Problem Due is March ??, 2017

EXAMS

Additional Classes: co-NP class (by --)
Class PS problems (by --)
PS-completeness (by --)
Randomized Turing Machines (by --)
Classes RP and ZPP (by --)
Primality Testing (by --)
More Applications of Regular Expression (by --)
Parallel Computation (by --)
X-Machine Testing (by --)
Probabilistic Computation (by --)
DNA Computing (by --)
Distributed computing with Turing Machine (by --)
An introduction to term rewriting systems and their applications (by --)