CSC 320 Class Notes: Summer 2012

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. [Powerpoint version].
  2. Lecture 2: Review of induction. [Powerpoint version].
  3. Lecture 3: More on induction. [Powerpoint version].
  4. Lecture 4: Countable and Uncountable Sets. [Powerpoint version].
  5. Lecture 5: Mathematics of computation. [Powerpoint version].
  7. Lectures 6 and 7: Regular Languages. [Powerpoint version].
  8. Lecture 8: Deterministic Finite Automata. [Powerpoint version].
  9. Lecture 9: Non-deterministic Finite Automata. [Powerpoint version].
  10. Lecture 10: Conversion of NDFA's to DFA's. [Powerpoint version].
  11. Lecture 11: Closure properties of regular languages. [Powerpoint version].
  12. Lecture 12: The pigeonhole principle. [Powerpoint version].
  13. Lecture 13: The proof of the pumping lemma. [Powerpoint version].
  14. Lecture 14: Using the pumping lemma. [Powerpoint version].
  15. Lecture 15: Questions about regular languages. [Powerpoint version].
  16. Lecture 16: Context-free grammars. [Powerpoint version].
  17. Lecture 17: Parse Trees. [Powerpoint version].
  18. Lecture 18: Pushdown Automata. [Powerpoint version].
  19. Lecture 19: Examples of Context-Free Languages. [Powerpoint version].
  20. Lecture 20: Examples of Context-Free Languages. [Powerpoint version].
  21. Lecture 21: Closure Properties for Context-Free Languages. [Powerpoint version].
  22. Lecture 22: The Pumping Theorem. [Powerpoint version].
  23. Lecture 23: Introduction to Turing Machines. [Powerpoint version].
  24. Lecture 24: More Turing Machines. [Powerpoint version].
  25. Lecture 25: Machine Schema. [Powerpoint version].
  26. Lecture 26: Closure Properties for Context-free Languages. [Powerpoint version].
  27. Lecture 27: Closure Properties for Turing Decidable Languages. [Powerpoint version].
  28. Lecture 28: Satisfiability (SAT). [Powerpoint version].
  29. Lecture 29: Universal Turing Machines. [Powerpoint version].
  30. Lecture 30: Encoding Turing machines to get "M". [Powerpoint version].
  31. Lecture 31: Two-way infinite tape, more on closure. [Powerpoint version].
  32. Lecture 32: The Halting Problem. [Powerpoint version].
    Some additional notes doing a similar proof in terms of C Programs that will not be covered this term are available here:
    The Halting Problem: C Program version. [Powerpoint version].
  33. Lecture 33: Proving problems are not decidable. [Powerpoint version].
  34. Lecture 34: Proving problems are NP-complete. [Powerpoint version].
  35. Lecture 35: Proving problems are NP-complete. [Powerpoint version].
CSC 320 Notes / maintained by Wendy Myrvold / wendym@csc.UVic.ca / revised Aug. 2, 2012