September 3: | Course Overview |
slides | notes |

September 5: | Induction and Strings |
slides | |

September 8: | Deterministic Finite Automata (DFAs) |
Not available yet | |

September 10: | Regular Languages |
slides | |

September 12: | Non-deterministic Finite Automata (NFAs) |
slides | latex source |

September 15: | Equivlance of NFAs and DFAs |
slides | |

September 17: | Regular Expressions = Finite Automata |
slides | |

September 19: | Regular Expressions and Non-Regular Languages |
slides | |

September 22: | The Pumping Lemma |
slides | |

September 24: | Context Free Languages |
slides | |

October 3: | Pumping Lemma for CFLs |
slides | |

October 6: | Regular Language Review |
notes | |

October 17: | Introduction to Turing Machines |
slides | |

October 20: | Fun with Turing Machines |
slides | |

October 22: | Turing Machine Variants |
slides | |

October 24: | Decidability |
slides | |

October 27: | Universal Turing Machines and Diagonalization |
slides | |

October 29: | The Halting Problem for Turing Machines |
slides | |

October 31: | Reductions |
slides | |

November 3: | Midterm Review |
no slides | |

November 5: | Midterm 2 |
questions | answers |

November 7: | Reductions Redux |
slides | |

November 10: | Computational Histories |
slides | |

November 12: | The Post Correspondence Problem |
slides | |

November 14: | Time Complexity, |
slides | |

November 17: | The Cook-Levin Theorem |
slides | |

November 24: | Cryptography |
slides | |

November 26: | More NP-Completenss Examples |
slides | |

November 28: | Research Advertisement |
slides |

Back to CpSc 421 home.