Complexity

What efficient algorithms cannot do: decision problems, polynomial-time reductions and NP-completeness, then approximation algorithms that come with a guarantee when exact answers are out of reach.

This part builds on Graphs and Algorithm design.

0 of 2 topics ready, listed in reading order

P and NPDecision problems, polynomial-time reductions, NP-completeness and satisfiability, with reductions written as code.Planned

Approximation algorithmsVertex cover, the metric travelling salesman problem and set cover, each with its guarantee proved and measured.Planned