Part X · Computational Geometry and Advanced Algorithms
61. Algorithmic Complexity Theory and Approximation
7 lessons•33 topics•Advanced / Expert
0 of 7 lessons published
61.01Outline
Problem classes
- P
- NP
- co-NP
- NP-hard
- NP-complete
- Decision vs optimization problem
61.02Outline
Reductions
- Polynomial-time reduction
- Mapping reduction
- NP-completeness proof pattern
61.03Outline
Classic hard problems
- SAT
- 3-SAT
- Vertex cover
- Independent set
- Clique
- Set cover
- TSP
- Subset sum
61.04Outline
Approximation algorithms
- Approximation ratio
- Vertex cover 2-approx
- Greedy set cover
- Metric TSP approximation overview
61.05Outline
Parameterized algorithms
- Fixed-parameter tractability
- Kernelization intro
- Search-tree branching
- Treewidth intuition
61.06Outline
Complexity beyond Big O
- Worst-case lower bounds
- Comparison model
- Adversary arguments
- Space complexity overview
61.07Outline
Algorithm design trade-offs
- Exact vs approximate
- Exponential but practical
- Meet-in-the-middle
- Heuristics vs guarantees