-
-
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
-
2.2 Dynamic Programming » Max Weight Independent Set interactive
Max Weight Independent Set
Try out solutions to find the max weight independent set in a different graph.
Exploring the model
-
The numbers of each node indicate its weight. The goal is to maximize the weight of the independent set.
-
Click on nodes in the graph to select them as members of the set. The chosen nodes will appear to the right, as members of the independent set. The weight of the independent set appears at the top.
-
When nodes are selected as members of the independent set, they turn green. White nodes can be selected; they are not connected to any selected nodes and thus maintain the independence of the set. Pink nodes are connected to nodes in the set and thus can not become members of the set without violating its independence.
-
Click the "restart" button in the upper left to re-set the graph.