Skip to content

Latest commit

 

History

History
233 lines (196 loc) · 7.37 KB

syllabus.md

File metadata and controls

233 lines (196 loc) · 7.37 KB
Raw

Table of Contents

Lecture 1: 9/30

  • Topics:
    • Sipser 2nd ed pgs 31 - 44
    • Sipser 3rd ed - same
    • Administrative Issues
    • What is computation?
    • Informal definition of computable function
    • Informal introduction to DFAs
    • Formal definition of DFAs + examples
    • Worksheet 1: Basic DFAs and Proofs
  • Admin:
    • Introduction to course
    • Goals of the course
    • Grading policy
    • Homeworks (plural) assigned

Lecture 2: 10/2

  • Topics:
    • Sipser 2nd ed pgs 44 - 62
    • Sipser 3rd ed pgs same
    • More DFA examples
    • Informal introduction to NFAs
    • Formal definition of NFAs
    • Examples of NFAs
    • Definition of regular languages
    • Construction of Union and Intersection for DFAs
    • Worksheet 2: NFAs and Basic Constructions

Lecture 3: 10/7

  • Topics:
    • Equivalence between of NFAs and DFAs
    • Constructions on NFAs and DFAs
      • Union for NFAs (and why intersection is hard)
      • Concatenation
      • Complement
      • Kleene star
    • Worksheet 3: Equivalence of NFAs and DFAs

Lecture 4: 10/9

  • Topics:
    • Sipser 2nd ed pgs 63 - 76
    • Sipser 3rd ed pgs 63 - 76
    • Introduction to RegExps
    • Examples of RegExps
    • Matching regexp as inductive predicate
    • Sketch of equivalence between RegExps/NFAs
    • Introducing examples of non-regular languages
    • Worksheet 4: Regular Expressions

Lecture 5: 10/14

  • Topics:
    • Sipser 2nd ed pgs 77 - 82, 99 - 106
    • Sipser 3rd ed pgs 77 - 82, 101 - 111
    • Definition of the pumping lemma
    • Examples of using the pumping lemma
    • Worksheet 5: Pumping Lemma

Lecture 6: 10/16

  • Topics:
    • Sipser 2nd ed pgs 107 - 127
    • Sipser 3rd ed pgs 111 - 129
    • Unintended study hall

Lecture 7: 10/21

  • Topics:
    • Sipser 2nd ed pgs 137 - 148
    • Sipser 3rd ed pgs 165 - 175
    • Introduction to Context-Free Languages
    • Introduction to context-free grammars
    • Formal definition of context-free grammars
    • Examples of CFGs
    • Chomsky Normal Form
    • Worksheet 6: Context Free Grammars
  • Admin:
    • HW 1 due
    • HW 1 solutions distributed

Lecture 8: 10/23

  • Topics:
    • Sipser 2nd ed pgs 149 - 159, 165 - 172
    • Sipser 3rd ed pgs 176 - 187, 193 - 201
    • PDAs
    • Examples of PDAs
    • CFG to PDA conversion
    • Worksheet 7: PDAs and Equivalence of CFGs and PDAs

Lecture 9: 10/28

  • Topics:
    • CFL pumping lemma
    • Examples thereof
    • Worksheet 8: CFL pumping lemma

Lecture 10: 10/30

  • Topics:
    • Introduction to Turing machines
    • Discussion of informal descriptions vs. state machines
    • First Examples of Turing machines
    • Deciders vs. Recognizers
    • Examples of state machine descriptions for Turing machines
    • More examples of informal descriptions
      • What is allowed in an informal description?
      • Machines simulating other machines
    • Worksheet 9: Turing Machines

Lecture 11: 11/4

  • Topics:
    • Variants of Turing machines
      • multi-tape
      • Non-deterministic Turing machines/non-deterministic choice
    • Examples of languages that are decidable
    • Examples of decidable use of non-deterministic choice
    • Worksheet 10: Practice with non-deterministic choice

Lecture 12: 11/6

  • Topics:
    • Sipser 2nd ed pgs 173 - 182
    • Sipser 3rd ed pgs 201 - 210
    • Goedel numberings
    • Proving that there exists a recognizable, but not decidable language
    • Other examples of recognizable languages
    • Languages that are neither recognizable nor decidable
      • \overline{ATM}
      • Proof that a recognizable, but not decidable language, has an unrecognizable complement
    • Worksheet 11: Diagonalization
  • Admin:
    • HW 2 due

Lecture 13: 11/13 (11/11 is Veteran's Day)

  • Topics:
    • Sipser 2nd ed pgs 206 - 211
    • Sipser 3rd ed pgs 234 - 238
    • Computable functions
    • Computable functions as algorithms
    • Computable reductions
    • Examples of computable reductions
    • Properties of computable reductions
    • Worksheet 10: Computable Functions and Reductions

Lecture 14: 11/18

  • Topics:
    • Sipser 2nd ed pgs 206 - 211
    • Sipser 3rd ed pgs 234 - 238
    • More examples of computable reductions
    • Proving a language decidable with computable reductions
    • Proving a language recognizable with computable reductions
    • Proving a language undecidable
    • Proving a language unrecognizable

Lecture 15: 11/20

  • Topics:
    • Sipser 2nd ed pgs 247 - 256
    • Sipser 3rd ed pgs 275 - 284
    • Even more computable reductions
    • Intro to time complexity
    • Counting time complexity for Turing machines
    • O-notation
    • Complexity class of P
    • Examples of problems in P
  • Admin:
    • HW 3 due

Lecture 16: 11/25

  • Topics:
    • Sipser 2nd ed pgs 256 - 294 (just skim 283 on)
    • Sipser 3rd ed pgs 284 - 332 (just skim 311 on)
    • NP complexity class
    • Examples of problems in NP
    • Polynomial-time reductions
    • NP-hard
    • NP-complete
    • Proving a language is NP-complete

Lecture 17: 12/2 (11/27 is thanksgiving)

  • Topics:
    • Untyped lambda calculus
    • Evaluation rules
    • Church encodings
    • Y-combinator

Lecture 18: 12/4

  • Course Review
  • Admin:
    • Homework 4 due

Final Exam: 12/9 5:30-7:20pm