Part XI · Advanced Data Structures and Offline Techniques
66. Advanced Combinatorial and Search Algorithms
7 lessons•28 topics•Advanced / Expert
0 of 7 lessons published
66.01Outline
Meet-in-the-middle
- Split solution space
- Subset sum
- Closest subsequence sum
- Half-enumeration matching
66.02Outline
Branch and bound
- Upper/lower bounds
- Search ordering
- Pruning optimality
- Knapsack B&B
66.03Outline
Exact cover
- Algorithm X
- Dancing Links (DLX)
- Constraint incidence matrix
66.04Outline
Binary decision diagrams
- Decision graph basics
- Reduced ordered BDD
- State compression overview
66.05Outline
Game theory algorithms
- Nim
- Sprague-Grundy theorem
- Mex
- XOR of Grundy values
- Impartial games
66.06Outline
Minimax and adversarial search
- Minimax
- Alpha-beta pruning
- Move ordering
- Transposition tables
66.07Outline
SAT and constraint solving
- CNF
- DPLL overview
- Unit propagation
- Backtracking search
- CDCL overview