CS251
  • Docs
    •   Course Staff
    •   Syllabus
    •   How to Succeed in CS251
  • Lectures
      Part 1: Formalizing Computation
    •   Introduction
    •   Mathematical Reasoning and Proofs
    •   What Is Information
    •   Deterministic Finite Automata 1
    •   Deterministic Finite Automata 2
    •   Turing Machines
    •   Universality of Computation
    •   Limits of Counting
    •   Limits of Computation
    •   Limits of Human Reasoning
      • Part 2: Computational Complexity
    •   Time Complexity
    •   Introduction to Graphs
    •   Maximum Matchings
    •   Stable Matchings
    •   P vs NP, Part 1
    •   P vs NP, Part 2
    •   Probability Theory Basics 1
    •   Probability Theory Basics 2
    •   Randomized Algorithms Introduction
    •   Randomized Algorithms for Cut Problems
    •   Modular Arithmetic
    •   Cryptography
      • Part 3: Highlights of Theoretical Computer Science
    •   Algorithms for Hard Problems
    •   Extra Topics
    •   Quantum Computation
  • Text
    • Text Overview
      • Part 1: Formalizing Computation
    •   Proof-Writing Guidelines
    •   Induction Review
    •   Encodings and Problems
    •   Deterministic Finite Automata
    •   Turing Machines
    •   Uncountable Sets
    •   Undecidable Languages
    •   Unprovable Truths
      • Part 2: Computational Complexity
    •   Time Complexity
    •   Introduction to Graph Theory
    •   Matchings in Graphs
    •   Stable Matchings
    •   Polynomial-Time Reductions
    •   Non-Deterministic Polynomial Time
    •   Probability Theory Basics
    •   Randomized Algorithms
    •   Modular Arithmetic
    •   Cryptography
      • Part 3: Highlights of Theoretical Computer Science
      To be added...
  • Recitations
      Part 1: Formalizing Computation
    •   Recitation - Introduction
    •   Recitation - Finite Automata
    •   Recitation - Turing Machines
    •   Recitation - Undecidability
      • Part 2: Computational Complexity
    •   Recitation - Complexity and Graphs
    •   Recitation - NP
    •   Recitation - Probability
    •   Recitation - Randomized Algorithms
    •   Recitation - Cryptography
      • Part 3: Highlights of Theoretical Computer Science
      To be added...
  • Links
    •   Piazza
    •   Gradescope
    •   Office Hour Queue
    •   Lecture Playlist
    •   My Grades
  • Calendar