pproenca/dot-skills/computer-science-algorithms

Community Classical Computer Science Algorithms Best Practices

A practitioner-oriented reference for choosing and implementing classical algorithms and data structures correctly. Organized by execution-lifecycle impact: the earliest decisions (asymptotic class, data-structure choice) cascade through everything else, so the rules near the top of the table matter most.

Scope: the patterns that show up in everyday production code review, reasonable interview / contest problems, and the at-scale toolbox (sketches, streaming, distributed primitives) — not an exhaustive cover of CLRS. Topics intentionally outside the current version: network flow, modular arithmetic, Bellman-Ford and Floyd-Warshall as standalone rules, SCC (Tarjan/Kosaraju), computational geometry, FFT, Manacher / Z-function as standalone rules. They're flagged inline in the relevant rules.

Distilled from CLRS (Introduction to Algorithms, 4th ed.), Sedgewick & Wayne (Algorithms, 4th ed., Princeton), Skiena's Algorithm Design Manual, Laaksonen's Competitive Programmer's Handbook, cp-algorithms.com, and the USACO Guide.

When to Apply

Use these rules when:

• Choosing an algorithm or data structure for a new problem ("what's the right way to do X?")
• Reviewing code for hidden O(n²) blowup — repeated in-checks on lists, pop(0) on lists, string concatenation in loops, naive substring search
• Picking a DP state or recurrence, before writing the memoization
• Modeling a problem as a graph (BFS vs Dijkstra vs topological sort)
• Refactoring brute force / naive solutions that work on toy inputs but time out at scale
• Deciding whether greedy applies, or whether DP / branch-and-bound is required

Rule Categories By Priority

Quick Reference

1. Asymptotic Complexity & Algorithm Selection (CRITICAL)

• `comp-pick-algorithm-class-from-input-bound` — Match O() to n before writing code
• `comp-amortize-instead-of-worst-casing` — Total cost, not per-op worst case
• `comp-watch-for-quadratic-blowup-from-membership-in-list` — Linear in checks in loops are O(n²)
• `comp-prefer-iterative-builders-over-string-concatenation` — Join / buffers, not +=
• `comp-derive-recurrences-via-master-theorem` — Write the recurrence before coding recursion
• `comp-treat-space-complexity-as-first-class` — Memory kills services before time does

2. Data Structure Selection (CRITICAL)

• `ds-hash-map-for-keyed-lookup` — Build the index once, then O(1) lookups
• `ds-set-for-uniqueness-and-membership` — Dedup and "have I seen this?" in O(1)
• `ds-heap-for-top-k-and-priority-queues` — O(n log k), priority-queue idioms
• `ds-deque-for-both-end-operations` — O(1) pop-front for BFS queues and sliding windows
• `ds-balanced-bst-or-sorted-container-for-range-queries` — Predecessor / successor / range scan
• `ds-union-find-for-dynamic-connectivity` — Near-O(1) grouping and merging
• `ds-prefix-sums-for-repeated-range-sums` — O(1) range sum after O(n) preprocessing
• `ds-fenwick-or-segment-tree-for-mutable-range-queries` — O(log n) updates + queries

3. Sorting & Searching (HIGH)

• `srch-use-builtin-sort-not-hand-rolled` — Timsort / introsort beat any hand-roll
• `srch-binary-search-on-sorted-data` — bisect, plus binary search on the answer
• `srch-quickselect-for-k-th-element` — O(n) average for k-th / median
• `srch-counting-and-radix-sort-for-bounded-integer-keys` — Beat O(n log n) for integer keys
• `srch-two-pointers-on-sorted-data` — O(n) on sorted arrays, sliding window

4. Dynamic Programming (HIGH)

• `dp-memoize-overlapping-subproblems` — @cache collapses exponentials
• `dp-tabulate-when-recursion-depth-or-order-matters` — Bottom-up + rolling arrays
• `dp-define-state-precisely` — Underspecified state = silent wrong answers
• `dp-knapsack-pattern` — 0/1 vs unbounded; loop direction is correctness
• `dp-bitmask-for-small-set-states` — n! → 2ⁿ · poly for n ≤ ~20
• `dp-prove-optimal-substructure-before-coding` — DP requires substructure; verify before coding

5. Graph Algorithms (HIGH)

• `graph-bfs-for-unweighted-shortest-path` — O(V+E), no heap needed
• `graph-dijkstra-for-non-negative-weights` — Lazy-deletion heap variant
• `graph-topological-sort-for-dependency-order` — Kahn's algorithm + DAG DP
• `graph-represent-as-adjacency-list-not-matrix` — Sparse graphs need lists
• `graph-detect-cycles-during-dfs` — Three-colour scheme for directed graphs
• `graph-kruskal-or-prim-for-mst` — MST with Union-Find or heap

6. Divide & Conquer / Recursion (MEDIUM-HIGH)

• `divide-merge-sort-pattern-for-counting-inversions` — Piggy-back counting onto the merge step
• `divide-watch-recursion-depth-and-stack` — Iterate, or raise the stack
• `divide-meet-in-the-middle-for-subset-problems` — 2ⁿ → 2^(n/2)
• `divide-quickselect-vs-quicksort-partitioning` — Random pivots; 3-way Dutch flag

7. Greedy Algorithms (MEDIUM)

• `greedy-prove-exchange-argument-before-using` — Greedy needs a correctness proof
• `greedy-sort-by-the-right-key-for-scheduling` — Finish time, deadline, value/weight
• `greedy-interval-merge-and-sweep-line` — Events + sort + linear sweep
• `greedy-huffman-and-priority-queue-greedies` — Heap-based "pick smallest repeatedly"

8. String & Sequence Algorithms (MEDIUM)

• `str-kmp-or-builtin-find-not-naive-search` — Linear worst-case substring search
• `str-trie-for-prefix-queries` — Autocomplete in O(|query|)
• `str-rolling-hash-for-multiple-substring-comparisons` — Two independent hashes, please
• `str-suffix-array-or-automaton-for-substring-queries` — Heavy-duty substring tooling

9. Scale & Probabilistic Algorithms (MEDIUM)

The "unusual but valuable at scale" toolbox — sketches that trade tiny accuracy loss for orders-of-magnitude memory wins, streaming primitives for inputs that don't fit in RAM, and distributed structures that survive sharding changes.

• `scale-bloom-filter-for-probabilistic-membership` — 1 bit/element vs 8 bytes, 1% false-positive rate
• `scale-hyperloglog-for-cardinality-estimation` — Count distinct over billions in ~12 KB
• `scale-count-min-sketch-for-frequency-estimation` — Heavy hitters and frequency queries in fixed memory
• `scale-reservoir-sampling-for-streams` — Uniform k-sample from a stream of unknown length
• `scale-consistent-hashing-for-distributed-sharding` — Remap k/n keys (not all keys) on node changes
• `scale-external-merge-sort-for-out-of-memory-data` — Sort 1 TB on 8 GB of RAM
• `scale-aho-corasick-for-multi-pattern-search` — Find all of m patterns in one pass over text
• `scale-minhash-lsh-for-near-duplicate-detection` — Near-duplicate pairs in O(n), not O(n²)

How to Use

Start with the category that matches the question:

• "What's the right algorithm for n = 10⁶?" → comp- (input-bound)
• "I'm looking things up in a list inside a loop" → ds-hash-map-for-keyed-lookup or comp-watch-for-quadratic-blowup-from-membership-in-list
• "My recursion is slow" → dp-memoize-overlapping-subproblems and comp-derive-recurrences-via-master-theorem
• "Shortest path / connectivity / ordering tasks" → graph-
• "Choose items to maximize value" → start with greedy-prove-exchange-argument-before-using; fall back to dp-knapsack-pattern
• "Find / match strings" → str-
• "Memory is the constraint, not time" / "Sample / count / deduplicate at scale" / "Sharding" → scale-

Code examples are in Python (most readable across audiences). The reasoning generalizes to any language — equivalent stdlib primitives are listed where they differ.

Reference Files