cs-foundationslisted
Install: claude install-skill rustcircle/c101
# CS foundations
Foundational claims are cheap to state and expensive to get wrong: a "linear" algorithm that is
quadratic on adversarial input, an NP-hardness proof reduced in the wrong direction, a consensus
design that loses acknowledged writes under a partition. This skill gives the selection tables
and the proof obligations; every answer states its model (input model, machine model, failure
model, consistency model) before its conclusion.
## 0. Triage
| Request | Section |
|---|---|
| Design an algorithm / pick a paradigm | 1 |
| Analyse running time, prove a bound | 2, 3 |
| "Is this NP-hard?", "Can we do better?" | 3, 4, [complexity and reductions](references/complexity-reductions.md) |
| Pick a data structure | 5, [data structures](references/data-structures.md) |
| Regex, parsing, grammar, decidability | 6 |
| Type system or compiler question | 7, 8 |
| Replication, consensus, consistency, clocks | 9, [distributed systems](references/distributed-systems.md) |
| Races, deadlocks, memory ordering | 10 |
| Specify and check a design | 11, [formal methods](references/formal-methods.md) |
## 1. Algorithm design paradigms
| Problem signal | Paradigm | Proof obligation |
|---|---|---|
| Optimal solution composed of optimal sub-solutions, subproblems repeat | dynamic programming | state definition, recurrence, order of evaluation, base cases; count states × transition cost |
| Local choice never needs revisiting | greedy | exchange argument or matroid structure; find a