Theory of Computation - CS 6/79995

T R 03:45 pm - 05:00 pm

HDN 106

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 Rostislav Pogrebinsky)	1(pdf)    2(pdf)
Regular Languages	1(pdf)    2(pdf)
Non-Regular Languages	1(pdf)    2(pdf)
Application of Regular Expressions  (by K.Nikhil Kumar)	1(pdf)    2(pdf)
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 Mahender Reddy Gangu)	1(pdf)    2(pdf)
Turing Machines	1(pdf)   2(pdf)
Variants of Turing Machine	1(pdf)    2(pdf)
PDA with the ability to flip its stacks  (by Bhargavi Belathur Ramalingaiah)	1(pdf)    2(pdf) (paper)
Markup Languages & XML  (by Vishal Kamtam Venkatesh)	1(pdf)    2(pdf)
Algorithms and Turing Machines	1(pdf)    2(pdf)
Decidable Languages	1(pdf)    2(pdf)
Turing Machines and Computers  (by Ravi Teja Pampana)	1(pdf)    2(pdf)
Undecidable Languages	1(pdf)    2(pdf)
Reducibility	1(pdf)    2(pdf)
Post's Correspondence Problem is Undecidable  (by Bharath Bhushan Reddy Goulla)	1(pdf)    2(pdf)
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 Manasa Kothakapu)	1(pdf)    2(pdf)

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 

---

1. Homework #1 (distributed in class) (due on 02/03/2015)
2. Homework #2 (distributed in class) (due on 02/12/2015)
3. Homework #3 (distributed in class) (due on 02/26/2015)

Extra Credit Problem Due is March 19, 2015

(see last slide in Variants of Turing Machine)

---

EXAMS

---

1. Tuesday, March 17, 2015, 03:45 - 05:00 p.m.  (possible questions)
2. Wednesday, May 6, 2015, 7:45 - 10:00 a.m. (possible questions)

Additional Classes: co-NP class  (by Krishna Mahesh Deevela Murali)	1(pdf)   2(pdf)
Class PS problems  (by Ram Babu Chelikani)	1(pdf)   2(pdf)
PS-completeness  (by Teja Sudha Gariganti)	1(pdf)   2(pdf)
Randomized Turing Machines  (by Farah Kamw)	1(pdf)   2(pdf)
Classes RP and ZPP   (by Sarika Pammi)	1(pdf)   2(pdf)
Primality Testing  (by Prabhat Vyas)	1(pdf)   2(pdf)
More Applications of Regular Expression (by Venkata Sai Pundamalli)	1(pdf)   2(pdf)
Parallel Computation (by Abdul Mobin)	1(pdf)   2(pdf)
X-Machine Testing (by Venkateswara Reddy. Tallapu Reddy)	1(pdf)   2(pdf)
Probabilistic Computation (by Remanth Kumar Dabbati)	1(pdf)   2(pdf)
DNA Computing (by Divya Tadesera)	1(pdf)   2(pdf)
Distributed computing with Turing Machine (by Xu Han)	1(pdf)   2(pdf)
An introduction to term rewriting systems and their applications (by Christian Newman)
More Applications of Context Free Grammars (by Bramara Manjeera)

---

F. Dragan
dragan (at) cs.kent.edu
Spring 2015