Theory of Computation - CS 6/76202

 

Topics    Slides per Page 
Introduction   1(ps) 1(pdf)    2(ps) 2(pdf)
Finite Automata   1(ps) 1(pdf)    2(ps) 2(pdf)
Finite Automata (cont.)   1(ps) 1(pdf)    2(ps) 2(pdf)
Application of FA's 
(by Andrian Marcus) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
Regular Languages   1(ps) 1(pdf)    2(ps) 2(pdf)
Non-Regular Languages   1(ps) 1(pdf)    2(ps) 2(pdf)
Application of Regular Expressions 
(by Anthony L. Martinez) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
Context-Free Grammars   1(ps) 1(pdf)    2(ps) 2(pdf)
Pushdown Automata   1(ps) 1(pdf)    2(ps) 2(pdf)
Non-Context-Free Languages   1(ps) 1(pdf)    2(ps) 2(pdf)
Application of Context-Free Grammars 
(by Saleh Al-shomrani) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
Turing Machines   1(ps) 1(pdf)    2(ps) 2(pdf)
PDA with the ability to flip its stacks 
(by Alice J. Lewis) 		  1(ps) 1(pdf)    2(ps) 2(pdf)  (paper)
Markup Languages & XML 
(by Louis Feng) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
Variants of Turing Machine   1(ps) 1(pdf)    2(ps) 2(pdf)
Algorithms and Turing Machines   1(ps) 1(pdf)    2(ps) 2(pdf)
Decidable Languages   1(ps) 1(pdf)    2(ps) 2(pdf)
Turing Machines and Computers 
(by Joseph Melnyk) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
Undecidable Languages   1(ps) 1(pdf)    2(ps) 2(pdf)
Reducibility   1(ps) 1(pdf)    2(ps) 2(pdf)
Post's Correspondence Problem is Undecidable 
(by Ganta Niveditha) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
Time Complexity   1(ps) 1(pdf)    2(ps) 2(pdf)
Complexity Classes P and NP   1(ps) 1(pdf)    2(ps) 2(pdf)
NP-completeness; The Cook-Levin Theorem   class handouts
More NP-complete Problems 
(by Ganta Niveditha) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
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) (discussion on 01/30/2002)
  2. Homework #2 (distributed in class) (discussion on 02/13/2002)
  3. Homework #3 (distributed in class) (discussion on 03/04/2002)
EXAMS
  1. Wednesday, March 20, 2002, 06:15 - 07:30 p.m.  
  2. Monday, May 6, 2002,  5:45 - 8:00 pm
Additional Classes: co-NP class 
(by Irina Lomonosov) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
Class PS problems 
(by Alice J. Lewis) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
PS-completeness 
(by Saleh Al-shomrani) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
Randomized Turing Machines 
(by Anthony L. Martinez) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
Classes RP and ZPP  
(by Joseph Melnyk) 		  1(ps) 1(pdf)    2(ps) 2(pdf)
Primality Testing 
(by Andrian Marcus and Louis Feng) 		  1(ps) 1(pdf)    2(ps) 2(pdf)

F. Dragan
dragan@cs.kent.edu
Spring 2002