CS421: Lecture Notes (Term 1, 2006/07)

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, P and NP 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.