CSC 320 Class Notes: Summer 2017

For a complete set of notes, please attend class or get notes from someone who attended. Only selected notes will be placed here.

  1. Lecture 1: Introduction to CSC 320.
  2. Lecture 2: Hamilton cycles and induction.
  3. Lecture 3: To infinitiy and Beyond.
  4. Lecture 4: Mathematics of computation.
  5. Lecture 5: Regular Languages.
  6. Lecture 6: DFA's.
  7. Lecture 7: Nondeterministic Finite Automata.
  8. Lecture 8: Converting a NDFA into a DFA.
  9. Lecture 9: Closure properties.
  10. Lecture 10: Proof of the Pumping Lemma.
  11. Lecture 11: Using the Pumping Lemma.
  12. Lecture 12: Context-free grammars.
  13. Lecture 13: Questions about regular languages.
  14. Lecture 14: Parse trees
  15. Lecture 15: Pushdown Automata
  16. Lecture 16: CFG's and PDA's
  17. Lecture 17: Closure properties for context-free languages
  18. Lecture 18: More PDA examples
  19. Lecture 19: The pumping theorem for context-free languages
  20. Lecture 20: Turing machines.
  21. Lecture 21: More Turing machines.
  22. Lecture 22: Machine Schema for TM's
  23. Lecture 23: Closure properties for Turing-decidable languages
  24. Lecture 24: Extensions to TM's and UTM's
  25. Lecture 25: Weird happenings with self-reference
  26. Lecture 26: Halting problem reductions
  27. Lecture 27: Introduction to NP-completeness
  28. Lecture 28: Vertex Cover is NP-complete
  29. Lecture 29: Finding Hamilton Cycles with a SAT solver
  30. Lecture 30: SAT is NP-complete (Cook's Theorem)

CSC 320 Notes / maintained by Wendy Myrvold / wendym@uvic.ca / revised July 25, 2017