---
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

| # | Title | Key topics |
|---|-------|-----------|
| [ch01](chapters/ch01-complexity-analysis.md) | Complexity & Analysis | RAM model, Big-Oh/Ω/Θ, tilde, growth rates, doubling test |
| [ch02](chapters/ch02-data-structures.md) | Fundamental Data Structures | arrays vs linked, stacks/queues/bags, dictionaries, hashing, ADTs/iterators |
| [ch03](chapters/ch03-sorting.md) | Sorting | selection/insertion/shell, mergesort, quicksort (3-way), lower bound, system sorts |
| [ch04](chapters/ch04-searching-symbol-tables.md) | Searching & Symbol Tables | binary search, BST, 2-3 & red-black trees, hash tables, cost summary |
| [ch05](chapters/ch05-priority-queues-heaps.md) | Priority Queues & Heaps | binary heap, swim/sink, heapsort, indexed PQ |
| [ch06](chapters/ch06-graphs.md) | Graphs — Representation & Traversal | adjacency list/matrix, BFS, DFS, topological sort, components, bipartite, SCC |
| [ch07](chapters/ch07-weighted-graphs.md) | Weighted Graphs | MST (Prim/Kruskal), shortest paths (Dijkstra/Bellman-Ford/Floyd), network flow, matching |
| [ch08](chapters/ch08-strings.md) | Strings | LSD/MSD/3-way string sort, tries/TST, KMP/Boyer-Moore/Rabin-Karp, regex/NFA, Huffman/LZW |
| [ch09](chapters/ch09-divide-conquer-dynamic-programming.md) | Divide & Conquer + Dynamic Programming | recurrences, memoization, optimal substructure, edit distance, LIS |
| [ch10](chapters/ch10-greedy-backtracking-heuristics.md) | Greedy, Backtracking & Search | exchange arguments, backtracking skeleton, pruning, local search, simulated annealing |
| [ch11](chapters/ch11-intractability-np.md) | Intractability & NP-Completeness | P/NP/NP-complete, reductions, SAT, Cook-Levin, approximation |
| [ch12](chapters/ch12-algorithm-catalog.md) | Algorithm Catalog (lookup) | Skiena's 75-problem "what to use" reference table |

## 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](glossary.md) — ~65 terms with definitions and chapter refs
- [patterns.md](patterns.md) — algorithmic design patterns (when / how / trade-offs)
- [cheatsheet.md](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.