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

#	Category	Prefix	Impact	Why it cascades
1	Asymptotic Complexity & Algorithm Selection	comp-	CRITICAL	Wrong O() class makes every other optimization irrelevant
2	Data Structure Selection	ds-	CRITICAL	The container determines which operations are cheap
3	Sorting & Searching	srch-	HIGH	Foundation for greedy, two-pointer, sweep-line, binary-search-on-the-answer
4	Dynamic Programming	dp-	HIGH	Exponential → polynomial transformations
5	Graph Algorithms	graph-	HIGH	Networks, dependencies, routing, scheduling all reduce to graphs
6	Divide & Conquer / Recursion	divide-	MEDIUM-HIGH	Logarithmic-factor speedups; stack-depth and recurrence traps
7	Greedy Algorithms	greedy-	MEDIUM	Fast when correct, silently wrong when not
8	String & Sequence Algorithms	str-	MEDIUM	Pattern matching, parsing, substring queries
9	Scale & Probabilistic Algorithms	scale-	MEDIUM	Sketches, streaming, distributed primitives — situational, decisive when they apply

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

File	Description
references/_sections.md	Category definitions and ordering
assets/templates/_template.md	Template for new rules
metadata.json	Version and reference information
AGENTS.md	Auto-built TOC navigation

Related Skills

• complexity-optimizer — Static analysis that finds the patterns these rules diagnose