Lecturer: James F. Lynch
Office: SC381
Telephone: 2682374
email: jlynch@clarkson.edu
Office hours: MWF 9:30AM11:30PM
Lecture hours: MWF 1:00PM1:50PM Snell Hall 213
Text: Introduction to the Theory of Computation, by Michael
Sipser
OBJECTIVES
We will cover Chapters 05 in the text, and as much of Chapter 7 as time permits. Exercises and Problems from the text will also be assigned, and some class time will be devoted to discussion and working of some of these.
ASSESSMENT
Grading will be based on three exams and the final.
Three hourly exams: 
70% 
Final: 
30% 
Hourly exam dates: 
Wednesday, September 19 
Wednesday, October 17 

Wednesday, November 14 
SYLLABUS




August 27  Basic math,
finite automata 

0.1, 0.2, 0.5, 0.8 
September 3  Closure properties of regular languages, nondeterministic finite automata, regular expressions 


10 
Regular
expressions, pumping lemma for regular languages 



Review, Exam I, 



Ambiguity
of contextfree grammars, Chomsky normal form 


October 1 
Fall
break,
Pushdown automata 



Pumping
lemma for contextfree languages, Turing machines 



Review, Exam II, 



Nondeterministic
Turing machines, algorithms, decidability 



Undecidability 


November 5 
Reducibility 



Review, 



Mapping reducibility, 



Time
complexity, P and NP 


December 3 
NP, Review 
