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.

Date | Topic/Assignment | Reading |
---|---|---|

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 |