algorithm-design-paradigmslisted
Install: claude install-skill rustcircle/c101
# Algorithm design paradigms
From statement to verified algorithm. DP technique lives in `dynamic-programming-patterns`, graphs in
`graph-algorithms`, proofs of bounds in `amortized-recurrence-analysis`, hardness in
`np-hardness-reductions`, randomness and sketches in `randomized-algorithms-sketches`; the hub is
`cs-foundations` section 1.
## 1. Formalisation template
Write this down before choosing anything:
| Field | Fill in |
|---|---|
| Input | types, n, m, value ranges (weights up to 10^9? negative? reals?) |
| Output | value only, or the witness (set, order, path) too |
| Objective | min / max / count (mod p?) / decide / enumerate all |
| Constraints | hard vs soft; ties; online or all input known; queries after preprocessing |
| Machine model | word RAM (w = 64), comparison only, external memory (B, M), work-span (W, D), streaming (one pass, sublinear space) |
| Budget | time limit, memory limit, latency percentile if it serves requests |
Size-to-budget table at ~10^8 simple operations per second per core (C++/Rust/Java; divide n by
roughly 10-50 for pure Python loops, or vectorise):
| n up to | Affordable | Typical algorithm |
|---|---|---|
| 10 | n! (3.6e6) | permutations, brute force |
| 20 | 2^n · n (2e7) | bitmask DP, subset enumeration |
| 40 | 2^(n/2) · n | meet in the middle |
| 500 | n^3 (1.25e8) | Floyd-Warshall, interval DP |
| 5 000 | n^2 (2.5e7) | pairwise DP, O(n^2) DP |
| 10^6 | n log n (2e7) | sorting, heaps, segment trees, Dijkstra |
| 10^8 | n |