CIS/MTH 465: Automata and Theory of Computation

Instructor: Andrew Kalafut
Email: kalafuta at gvsu dot edu
Office: C-2-210 MAK
Office hours: MWF 1:00-2:00

Please read the syllabus
Required text: Introduction to the Theory of Computation, Second Edition, by Michael Sipser

This web site should be considered an official form of communication for this class and should be checked often. The schedule posted below is subject to frequent change, depending on speed of coverage.

Schedule

DateTopic/AssignmentReading
M August 29, 2011 Course Introduction 0.1
W September 1, 2011 Mathematical Review 0.2 - 0.4
F September 3, 2011 Finite Automata 1.1
M September 5, 2011 No class - labor Day
W September 7, 2011 Nondeterministic Finite Automata 1.2
F September 9, 2011 Regular Expressions 1.3
M September 12, 2011 Assignment 1 due
W September 14, 2011 Nonregular Languages and Pumping Lemma 1.4
F September 16, 2011 Context Free Grammars 2.1
M September 19, 2011 Pushdown Automata 2.2
W September 21, 2011 Equivalence of CFG and PDA
F September 23, 2011 Non-context-free Languages 2.3
M September 26, 2011 Assignment 2 due
W September 28, 2011 Test 1
F September 30, 2011 Turing Machines 3.1
M October 3, 2011 Turing Machines (variants) 3.2
W October 5, 2011 Church-Turing Thesis 3.3
F October 7, 2011 Lambda Calculus
M October 10, 2011 Decidability 4.1
W October 12, 2011 Undecidable Problems 4.2
F October 14, 2011 Assignment 3 due
M October 17, 2011 Reducibility 5.1
W October 19, 2011 Reducibility (more) 5.2
F October 21, 2011 Mapping Reducibility 5.3
M October 24, 2011 Post Correspondance Problem
W October 26, 2011 Turing Reducibility 6.3
F October 28, 2011 Assignment 4 due
M October 31, 2011 Recursion Theorm 6.1
W November 2, 2011 Test 2
F November 4, 2011 Time Complexity 7.1
M November 7, 2011 Polynomial Time problems 7.2
W November 9, 2011 Test 2 discussion
F November 11, 2011 Review of reductions
M November 14, 2011 Test 2 redo
W November 16, 2011 Nondeterministic Polynomial Time problems 7.3
F November 18, 2011 NP-Completeness 7.4
M November 21, 2011 NP-Complete Problems 7.5
W November 23, 2011 Thanksgiving
F November 25, 2011 Thanksgiving
M November 28, 2011 NP-complete problems
W November 30, 2011 Space Complexity 8.1 - 8.3
F December 2, 2011 Logarithmic space Space 8.4 - 8.5
M December 5, 2011 Probablistic Algorithms 10.2
W December 7, 2011 Cryptography 10.6
F December 9, 2011 Assignment 5 due
W December 14, 2011 Test 3 (final) 2:00 - 3:50 PM