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