CS 81 Notes

Computability

• Introduction to Computability 10/18
• Strings 10/18
• State Machines 10/18
• Regular Languages and Regular Expressions 10/23
• Kleene's Theorem 10/23
• Closure Properties of (the set of) Regular Languages 10/25
• Extended Regular Expressions 10/30
• Nonregular Languages: Distinguishable Strings 10/30
• Nonregular Languages: Pumping Lemma 11/02
• Context-Free Languages (CFLs) 11/02
• Context-Free Grammars 11/06
• Parsing and Parse Trees 11/06
• Non-Context-Free Languages 11/08
• The CYK Algorithm 11/08
• Regular Grammars 11/08
• Extra: Unrestricted Grammars 11/13
• Turing Machines 11/13
• Decidability and Undecidability 11/15
• Semidecidability 11/15
• Reductions 11/20
• Mapping Reductions 11/20
• Rice's Theorem 12/30
• Computation Histories 12/30
• The Post Correspondence Problem 12/30

Propositional Logic

• Why Study Logic? 08/25
• Well-Formed Formulas of Propositional Logic 08/28
• Models of Propositional Logic 08/28
• Entailment 08/28
• Abbreviating WFFs 08/28
• Logic vs. English 08/28
• Proof Systems 08/30
• Natural Deduction - Introduction & Elimination Rules 08/30
• Natural Deduction - Classical Rules 09/05
• Resolution 12/28
• Metatheory 12/28

Predicate Logic

• Predicate Logic 09/11
• Predicate Formulas 09/11
• Natural Deduction in Predicate Logic 09/13

Doing Proofs

• Proofs for Humans 09/18
• Bounded Quantifiers 09/18
• Proofs with Implications and Equivalences 09/18
• Proofs with Quantifiers 09/18
• Asymptotic Analysis 09/18
• Mathematical Induction 09/20
• Preconditions, Postconditions, and Loop Invariants 10/02
• Countable Sets 10/09
• Uncountable Sets 10/09

Prolog

• Logic Programming 09/25
• Unification 09/25
• Depth-First Search in Prolog 09/25
• DFS Consequences 09/25
• Generate and Test 09/25
• Prolog to English 09/27
• Lists in Prolog 09/27
• Manipulating Lists 09/27
• Equality, Inequality, and Arithmetic in Prolog 09/27
• Negation in Prolog 09/27

Finally