Thurs Jan 22 | Course Description and mathematical background | |

Thurs Jan 29 | Finite Automata; Nondeterminism | Regular Expressions; Non-regular languages |

Thurs Feb 5 | Context-Free grammars and pushdown automata | |

Thurs Feb 12 | MidTerm exam | |

Thurs Feb 19 | the Church-Turing Thesis | |

Thurs Feb 26 | Decideable languages; the Halting Problem | |

Thurs Mar 5 | Reducibility | The Recursion Theorem |

Thurs Mar 12 No class: Spring Break | ||

Thurs Mar 19 | MidTerm exam | |

Thurs Mar 26 | Measuring complexity; the class P; the class NP | |

Thurs Apr 2 | NP-complete problems | |

Thurs Apr 9 | Space Complexity | |

Thurs Apr 16 | MidTerm exam | |

Thurs Apr 23 | Intractability | |

Thurs Apr 30 | Interactive Proof systems | Cryptography |

Thurs May 7 (last day of class) Final |