algos

name: algos description: "Combined knowledge base from "The Algorithm Design Manual" (Skiena) and "Algorithms, 4th Edition" (Sedgewick & Wayne). Use when choosing or analyzing an algorithm or data structure — complexity analysis, sorting, searching/symbol tables, heaps, graphs, shortest paths, strings, dynamic programming, greedy, backtracking, NP-completeness — when modeling a problem to a known algorithm, or when looking up the best-known approach for a problem." allowed-tools: - Read - Grep argument-hint: [topic, algorithm name, or chapter number]

Algorithms — Skiena + Sedgewick (combo)

Authors: Steven Skiena (The Algorithm Design Manual) + Robert Sedgewick & Kevin Wayne (Algorithms, 4th Ed.) | Pages: ~1,708 | Chapters: 12 (topic-merged) | Generated: 2026-06-07

How to Use This Skill

• Without arguments — load the Core Frameworks below for design/analysis judgment.
• With a topic — ask about dijkstra, red-black trees, dynamic programming, union-find; use the Topic Index to find the chapter, then read that chapters/chNN-*.md before answering.
• With a chapter — ask for ch06; load that file.
• "What's the best algorithm for X?" — check chapters/ch12-algorithm-catalog.md (Skiena's 75-problem lookup) first.

The two books are complementary, and the chapters preserve the contrast: Sedgewick = precise Java implementations, exact APIs, empirical/tilde cost analysis (reach for it to implement and measure). Skiena = problem modeling, when-to-use judgment, war stories, the catalog (reach for it to recognize what kind of problem you have and pick an approach).

Core Frameworks & Mental Models

1. Analyze before you optimize (complexity)

• RAM model + Big-Oh/Ω/Θ (Skiena) for classification; tilde ~ + order-of-growth (Sedgewick) for prediction. Big-Oh is only an upper bound — use ~ or Θ for tight claims, and the doubling-ratio test (T(2N)/T(N) → 2^b ⇒ order N^b; ratio ≈ 8 ⇒ cubic) to validate empirically.
• Dominance ladder (memorize): n! ≫ 2ⁿ ≫ n³ ≫ n² ≫ n lg n ≫ n ≫ lg n ≫ 1. Logs appear whenever you repeatedly halve the domain (binary search, balanced trees, divide & conquer).

2. Pick the right data structure first

• Contiguous (arrays) vs linked (Skiena): arrays give O(1) random access + cache locality; linked structures give O(1) splice + unbounded growth. Resizing arrays amortize to O(1) append.
• Symbol table = the workhorse. Sedgewick's cost summary: ordered BST → ~1.39 lg N avg but O(N) worst; red-black BST → guaranteed ~lg N for all ordered ops; hash tables → O(1) average (separate chaining or linear probing) but lose order. Default to a hash table for pure lookup, a balanced BST when you need ordered operations (floor/ceiling/range).
• Priority queue (binary heap): insert/del-max in ~lg N; the engine behind heapsort, Dijkstra, Prim, and "top-k" selection. Use an indexed PQ when you must decrease-key.

3. The five design techniques (Skiena Part I — the heart of design)

• Divide & conquer: split, recurse, combine; analyze with the recurrence (e.g. mergesort T(n)=2T(n/2)+n = Θ(n lg n)).
• Dynamic programming: when subproblems overlap and the problem has optimal substructure. Recipe: (1) define the recurrence/objective, (2) order subproblems so dependencies come first, (3) memoize or fill a table bottom-up. Canonical: edit distance, longest increasing subsequence. DP trades space for re-computation.
• Greedy: take the locally best choice; only correct when an exchange argument proves it (MST, Dijkstra, Huffman are provably greedy). Verify correctness or find a counterexample — greedy is wrong far more often than it looks.
• Backtracking: systematic DFS over the solution space (subsets, permutations, paths) with pruning; the general skeleton tests partial solutions and abandons dead branches early.
• Reduction: transform your problem into a solved one. Skiena's Take-Home Lesson: don't design novel graph algorithms — design graphs that let you call classical ones. Network flow subsumes bipartite matching; topological sort solves ordering-under-constraints.

4. Graphs are a modeling language

• Choose adjacency list (sparse, E ≈ V) vs matrix (dense, O(1) edge test). BFS → shortest unweighted paths, bipartite check, connected components. DFS → topological sort (reverse postorder), cycle detection, articulation points, strong components (Kosaraju/Tarjan). Weighted: MST (Prim eager ~E log V, Kruskal ~E log E + union-find), shortest paths (Dijkstra O(E log V) no negative edges; Bellman-Ford O(VE) handles negatives + detects negative cycles; DAG relaxation O(E+V); Floyd-Warshall O(V³) all-pairs).

5. Know when to stop (intractability)

• If your problem reduces from a known NP-complete problem (SAT, vertex cover, independent set, clique, Hamiltonian cycle, TSP), stop hunting for a polynomial algorithm. Switch to: approximation algorithms (with a proven ratio), heuristics (local search, simulated annealing), or exponential backtracking with hard pruning on small instances. Reduce in the correct direction (known-hard ⇒ yours) to prove hardness.

Chapter Index

Topic Index

• Amortized analysis / resizing arrays → ch01, ch02
• Approximation algorithms → ch11
• Articulation vertices / cut nodes → ch06
• Backtracking → ch10
• Bellman-Ford → ch07
• Big-Oh / Ω / Θ notation → ch01
• Binary search → ch01, ch03, ch04
• Binary search trees (BST) → ch04
• Bipartite detection / matching → ch06, ch07
• Boyer-Moore → ch08
• Breadth-first search (BFS) → ch06
• Connected / strong components (Kosaraju, Tarjan) → ch06
• Cost model / tilde notation → ch01
• Depth-first search (DFS) → ch06
• Dijkstra's algorithm → ch07
• Divide & conquer / recurrences → ch09 (analysis ch01, ch03)
• Dynamic programming (edit distance, LIS) → ch09
• Edit distance / approximate string matching → ch09, ch08
• Floyd-Warshall (all-pairs) → ch07
• Greedy algorithms / exchange argument → ch10 (applied ch07)
• Hash tables (chaining, linear probing) → ch02, ch04
• Heaps / heapsort → ch05, ch03
• Huffman / LZW compression → ch08
• Knuth-Morris-Pratt (KMP) → ch08
• Kruskal's algorithm → ch07
• Linked lists vs arrays → ch02
• Local search / simulated annealing → ch10
• Lower bound for sorting (N lg N) → ch03
• Minimum spanning tree (MST) → ch07
• NP-completeness / reductions / SAT → ch11
• Network flow (Edmonds-Karp, residual graph) → ch07
• Priority queues / indexed PQ → ch05
• Problem-to-algorithm lookup → ch12
• Quicksort (incl. 3-way) → ch03
• Rabin-Karp → ch08
• Red-black / 2-3 trees → ch04
• Regular expressions / NFA → ch08
• Shortest paths → ch07 (unweighted: ch06)
• Sorting (selection, insertion, shell, merge, quick) → ch03
• Stacks / queues / bags → ch02
• String sorts (LSD/MSD/3-way radix) → ch08
• Symbol tables / dictionaries → ch04, ch02
• Topological sort → ch06
• Tries / TST → ch08
• Union-find (weighted quick-union) → ch07, ch02

Supporting Files

• glossary.md — ~65 terms with definitions and chapter refs
• patterns.md — algorithmic design patterns (when / how / trade-offs)
• cheatsheet.md — master complexity tables + "which algorithm when"

Scope & Limits

Covers the two source books only. Every complexity bound and API in the chapter files was synthesized directly from the extracted text; specifics the source did not state are marked *(not found in source slice)* rather than guessed. For language-specific standard-library behavior or problems beyond these books, verify against current references. For implementation in a specific codebase, combine with project tooling.