Section F: Advanced Algorithms
This section covers cutting-edge algorithmic techniques that go well beyond standard interview DSA. Topics here appear in competitive programming World Finals, research papers, and specialized engineering roles (quant trading, compiler optimization, network infrastructure, database internals).
Topic Map
mindmap
root((Advanced Algorithms))
Network Flow
Min-Cost Max-Flow
Cost Scaling
Push-Relabel Variants
Dinic Optimizations
Dynamic Trees
Link-Cut Trees
Euler-Tour Trees
Top Trees
Dynamic MST
Tree Techniques
Centroid Decomposition
Heavy-Light Decomposition
DSU on Tree
Virtual Trees
Rerooting DP
DP Optimization
Knuth / Aliens Trick
Convex Hull Trick
Li Chao Tree
Divide & Conquer DP
Subset Convolution (SOS DP)
Polynomials
FFT / NTT / Bluestein
Multipoint Evaluation
Berlekamp-Massey
Linear Recurrences
Matrix Algorithms
Strassen / Coppersmith-Winograd
Randomized Linear Algebra
Sketching
Streaming & Sublinear
Count-Min / AMS Sketch
Distinct Counting
Property Testing
Approximation & FPT
PTAS / FPTAS
Kernelization
Treewidth
Graph Minors
Parallel & Graph
Cache-Oblivious
PRAM / Work-Span
Spectral Methods
Laplacian Solvers
Reading Order
Foundations vs. Advanced: What’s New
| Category | Covered in Base DSA (chapters/) | NEW in advanced/ |
|---|---|---|
| Flow | Ford-Fulkerson, Edmonds-Karp, Dinic, Push-Relabel, MCMF basics | Cost scaling, dynamic trees in flow, Dinic with current-arc + multithreading |
| Trees | HLD, centroid decomposition, LCA, link-cut basics | Virtual trees, tree hashing, DSU on tree, rerooting DP, small-to-large, top trees, Euler-tour trees |
| DP Opt | CHT, divide & conquer DP, Knuth | Aliens trick (parametric search), Li Chao tree, SOS DP, subset convolution, min-plus convolution, Monge/SMAWK |
| Polynomials | FFT, NTT basics | Bluestein FFT, multipoint evaluation, interpolation, formal power series |
| Matrices | Strassen overview, matrix exponentiation | Coppersmith-Winograd, tensor methods, randomized sketching |
| Streaming | Count-Min Sketch, HLL basics | AMS sketch, turnstile/sliding-window streams, sublinear algorithms, property testing |
| Approximation | PTAS definition, basic schemes | Kernelization, treewidth algorithms, graph minors, planar separators |
| Parallel | PRAM basics | Work-span model, work stealing, parallel prefix/sorting, spectral graph algorithms, Laplacian solvers |
Cross-References to Existing Content
- Graph fundamentals: Ch 22, Ch 28
- Network flow: Ch 29, Ch 83, Ch 169
- Trees: Ch 13, Ch 84, Ch 107, Ch 108
- DP: Ch 31, Ch 86, Ch 113, Ch 116, Ch 117, Ch 118, Ch 188
- Polynomials/FFT: Ch 167, Ch 171, fft-and-polynomial.md
- Matrices: Ch 73, Ch 174
- Probabilistic/streaming: Ch 79, Ch 147
- Approximation/parameterized: Ch 145, Ch 148, Ch 96
- Parallel/external: Ch 159, Ch 160
- Advanced DS: Ch 98, Ch 157, Ch 106, Ch 156
- Spectral: Ch 154