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)

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)

Variants of Turing Machine 

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

class handouts

More NP-complete Problems 
(by Manasa Kothakapu) 

1(pdf)    2(pdf)

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

Textbooks:

 

http://www.cs.kent.edu/~dragan/0201441241.jpg

http://www.cs.kent.edu/~dragan/sipser.gif

http://www.cs.kent.edu/~dragan/nullcover.gif

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 03/??/2015)

EXAMS

  1. Tuesday, March ?, 2015, 03:45 - 05:00 p.m.  
  2. Wednesday, May 6, 2015, 7:45 - 10:00 a.m.

 

 

 

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)

 

Parallel Computation (by Abdul Mobin)

 

X-Machine Testing (by Venkateswara Reddy. Tallapu Reddy)

 

Probabilistic Computation (by Remanth Kumar Dabbati)

 

DNA Computing (by Divya Tadesera)

 

(by Xu Han)

 

An introduction to term rewriting systems and their applications

(by Christian Newman)

 


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