Definitions Countability
Class 1: Introduction [Slides]
- Goals of the Course
- Adding and Multiplying
Class 2: Defining Definitions [Slides]
- Babylonian numbers
- Why study theory?
- Is 0 a Natural Number?
Class 3: What can be represented by bits? [Slides]
- Meaning of “optimal”
- Representing the numbers and binary strings
- Set cardinality
Class 4: More Infinities [Slides]
- Cantor’s Power Set cardinality theorem
- Implications of Cantor’s result
Finite Computation
Class 5: Defining Computation [Slides]
- Implications of Cantor’s ideas
- Defining Computation
Class 6: Modeling Boolean Circuits [Slides]
- Finite Computation
- Defining Boolean Circuits
- Universality
Class 7: Universal Circuits [Slides]
- Boolean Circuits Model Definition
- Universality of AON Boolean Circuits
Class 8: Syntactic Sugar, Complexity of Functions [Slides]
- Recap universality and syntactic sugar
- Asymptotic Notation
- Circuit Complexity: how many gates
- Existence of hard functions
Class 9: Circuit Size Hierarchy [Slides]
- Computing functions using LOOKUP
- Size Hierarchy
- Universal Circuit
Class 10: Circuit Complexity [Slides]
- Size Hierarchy Theorem
- Universal Circuit
Class 11: Universal Circuits [Slides]
- Universal Circuits
- Practice Problems
Class 12: Midterm Review [Slides]
Uniform Computation
Class 13: Finite Automata and Regular Expressions [Slides]
- Finite and Uniform Computation
- Introducing Finite Automata
Class 14: Regular Expressions [Slides]
- Finite Automata
- Regular Expressions
- Consequences of Equivalence of DFA and Regular Expressions
Class 15: Deterministic and Nondeterministic Finite Automata [Slides]
- Formalizing DFA
- Introducing Nondeterminism
- Converting a DFA to and NFA
Class 16: Completing the Proof, Bringing Down the Internet [Slides
- Extending the NFA model: NFA-ϵ
- Implemeting Python’s Regular Expression library
- Challenges implementing RE matching (Cloudflare incident)
Class 17: NFA vs. RE, Introducing Turing Machines [Slides]
- Completing the proof that Regular Expressions can be converted to NFA-ϵ
- Proving that DFAs can be converted to Regular Expression
- Introducing Turing Machine model of computation
Computability
Class 18: Turing Machines [Slides]
- Converting DFA to RE
- Turing Machines
Class 19: Computability [Notes] [Slides]
- Formal model of Turing Machine
- Are there functions that cannot be computed by a TM?
- Self-Rejecting
Class 20: Proving Uncomputability [Slides]
- Church-Turing Thesis
- Universal Machines
- ACCEPTS is Uncomputable
- Ali G (Computability and Practical Solvability)
Class 21: Reductions and Recognizability [Slides]
- Reduction Proofs
- Recognizability
- Non-recognizability of the complement of HALTS
Class 22: Rice’s Theorem [Slides]
- Recognizability
- Rice’s Theorem
- Kolmogorov Complexity
Complexity
- Cost of Computing
- Defining TIMETM(T(n))
- Class P
- Robustness of P
- Polynomial-Time Reductions
Class 24: Complexity II [Slides]
- Cook Reductions and Karp Reductions
- 3SAT and CircuitSAT
Class 25: Probably Hard Problems [Slides]
- Complexity classs NP
- Introducing the question is P a proper subset of NP (P = NP)?
- Cook-Levin Theorem
Class 26: Cook-Levin Theorem [Slides]
- Nondeterministic Turing Machines
- Proving the Cook-Levin Theorem
- Implications of P = NP