CSC 320 Class Notes: Fall 2011

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.
    Or click here if you prefer pdf.
  2. Lecture 2: Review of Induction.
    Or click here if you prefer pdf.
  3. Lecture 3: More on Induction
    Or click here if you prefer pdf.
  4. Lecture 4: Countable and Uncountable sets.
    Or click here if you prefer pdf.
  5. Lecture 5: Languages.
    Or click here if you prefer pdf.
  6. Lecture 6: Regular expressions.
    Or click here if you prefer pdf.
  7. Lecture 7: DFA's.
    Or click here if you prefer pdf.
  8. Lecture 8: DFA's.
    Or click here if you prefer pdf.
  9. Lecture 9: Conversion of NDFA's to DFA's.
    Or click here if you prefer pdf.
  10. Lecture 10: Closure properties of regular languages.
    Or click here if you prefer pdf.
  11. Lecture 11: The pigeonhole principle.
    Or click here if you prefer pdf.
  12. Lecture 12: Proof of the Pumping Lemma.
    Or click here if you prefer pdf.
  13. Lecture 13: Using the Pumping Lemma.
    Or click here if you prefer pdf.
  14. Lecture 14: Questions about Regular Languages.
    Or click here if you prefer pdf.
  15. Lecture 15: Context-free Grammars.
    Or click here if you prefer pdf.
  16. Lecture 16: Parse Trees.
    Or click here if you prefer pdf.
  17. Lecture 17: PDA's.
    Or click here if you prefer pdf.
  18. Lecture 18: More about context-free languages.
    Or click here if you prefer pdf.
  19. Lecture 19: Closure properties of context-free languages.
    Or click here if you prefer pdf.
  20. Creating a DFA with a minimum number of states.
  21. Lecture 21: Midterm Review.
    Or click here if you prefer pdf.
  22. Lecture 22: The pumping theorem.
    Or click here if you prefer pdf.
  23. Lecture 23: Closure properties of CFL's.
    Or click here if you prefer pdf.
  24. Lecture 24: Turing Machines.
    Or click here if you prefer pdf.
  25. Lecture 25: Turing Machines.
    Or click here if you prefer pdf.
  26. Lecture 26: Machine schema
    Or click here if you prefer pdf.
  27. Lecture 27: Closure properties for Turing-decidable languages
    Or click here if you prefer pdf.
  28. Lecture 28: Universal Turing machines
    Or click here if you prefer pdf.
  29. Lecture 29: An introduction to NP-completeness
    Or click here if you prefer pdf.
  30. Lecture 30: Self-reference
    Or click here if you prefer pdf.
  31. Lecture 31: The Halting Problem
    Or click here if you prefer pdf.
  32. Lecture 32:Satisfiability (SAT)
    Or click here if you prefer pdf.
  33. Lecture 33: On Tuesday Nov. 29, I will finish the notes from Lecture 31 on the Halting problem.
  34. Lecture 34: NP-Completeness (Wed.)
    Or click here if you prefer pdf.
  35. Lecture 35: SAT is NP-complete (Friday)
    Or click here if you prefer pdf.
CSC 320 Notes / maintained by Wendy Myrvold / wendym@csc.UVic.ca / revised Nov. 28, 2011