-
-
Course Introduction
-
Two Kinds of Paths
-
Polynomials vs. Exponentials
-
Divide and Conquer
-
Big O and All that
-
When the details don't matter
-
Quiz 1 (self-assessment)
-
-
-
Divide and Conquer Redux
-
Dynamic Programming
-
Greedy Algorithms
-
Landscapes
-
Reductions and Translations
-
Lessons So Far
-
The Best of All Possible Algorithms
-
Complexity Wrap-Up
-
Quiz 2 (self-assessment)
-
-
-
Finding versus Checking
-
Circuits and Formulas
-
More NP-complete Problems
-
P versus NP Problem
-
Existence and Nonexistence
-
Above and Beyond
-
Quiz 3 (self-assessment)
-
-
-
Real World Problems
-
Phase Transitions
-
Random Problems
-
Solvability Threshold
-
Modeling Differential Equations
-
Landscapes, Clustering, Freezing, and Hardness
-
Quiz 4 (self-assessment)
-
-
-
Building Blocks: Recursive Functions
-
Building Blocks: Partial Recursive Functions
-
λ Calculus
-
Turing Machines
-
The Halting Problem
-
The Grand Unified Theory of Computation
-
The Analytical Engine
-
Cellular Automata
-
Tile-Based Computation
-
Dynamical Systems
-
Quiz 5 (self-assessment)
-
-
-
More from Cris Moore
-
Other ComplexityExplorer resources
-
3.6 Above and Beyond » Complexity Hierarchy & Quiz Download Video
Note: the quiz at the end of the lecture will be used as an exam question, so there will be no solution video.