# Algorithms

An algorithm is a concrete method with an argument for its correctness
and a bound on its cost — the difference between a program that works on
your laptop and one that holds up at scale.


_Figure 001 — A* search: a heuristic steers the frontier toward the goal, then traces
the shortest path.
_

_Figure 002 — Why cost matters: n, n·log n, n², 2ⁿ.
_

Correctness comes first. Before you ask whether an algorithm is fast, you
ask whether it is right — an invariant that holds at every step, a base
case that grounds the recursion, an argument that the loop must end.


The core skill is then reasoning about **cost** before you
write a line of code. Asymptotic analysis lets you compare strategies on
paper and predict which scales to a million inputs and which becomes
impractical at a thousand.


_Figure 003 — Dynamic programming: an LCS table, filled cell by cell.
_

Big-O strips away the constants and the hardware to leave the one thing
that matters at scale: how the work grows as the input does. A linear pass
and a quadratic one are indistinguishable on ten items and orders of
magnitude apart on ten million.


Most hard problems yield to a handful of ideas — divide & conquer,
greedy choices, dynamic programming, and well-chosen data structures.
Learn the ideas once and you start to recognize them everywhere.


_Figure 004 — Model it as a graph and search.
_

Data structures are the other half. The right one — a heap, a hash
table, a balanced tree, a union-find — turns an expensive operation into
a cheap one.


_Figure 005 — Sorting: from jumbled to ordered, one comparison at a time.
_

And when a problem is genuinely intractable, you learn to _prove_
it — so you stop searching for an efficient algorithm that cannot exist, and
start designing approximations that can.


The subject teaches you to find a good solution, justify it, and know
when no better one is possible.


---

## Contents

### 1. Foundations

1. [What Is an Algorithm?](/algorithms/foundations/what-is-an-algorithm)
2. [Proof Techniques](/algorithms/foundations/proof-techniques)
3. [Asymptotic Analysis](/algorithms/foundations/asymptotic-analysis)
4. [Growth Rates and Loop Analysis](/algorithms/foundations/growth-rates-and-loop-analysis)
5. [Recurrences and the Master Theorem](/algorithms/foundations/recurrences)
6. [Amortized Analysis](/algorithms/foundations/amortized-analysis)

### 2. Divide & Conquer

1. [Divide and Conquer & Mergesort](/algorithms/divide-and-conquer/mergesort)
2. [Quicksort](/algorithms/divide-and-conquer/quicksort)
3. [Linear-Time Selection](/algorithms/divide-and-conquer/selection)
4. [Fast Multiplication](/algorithms/divide-and-conquer/fast-multiplication)

### 3. Sorting & Order Statistics

1. [Heaps and Heapsort](/algorithms/sorting/heaps-and-heapsort)
2. [Lower Bounds for Comparison Sorting](/algorithms/sorting/sorting-lower-bounds)
3. [Sorting in Linear Time](/algorithms/sorting/linear-time-sorting)
4. [External Sorting](/algorithms/sorting/external-sorting)

### 4. Data Structures

1. [Elementary Data Structures](/algorithms/data-structures/elementary-structures)
2. [Hash Tables](/algorithms/data-structures/hash-tables)
3. [Binary Search Trees](/algorithms/data-structures/binary-search-trees)
4. [AVL Trees](/algorithms/data-structures/avl-trees)
5. [Balanced Search Trees](/algorithms/data-structures/balanced-trees)
6. [Disjoint Sets (Union-Find)](/algorithms/data-structures/union-find)
7. [Fenwick & Segment Trees](/algorithms/data-structures/fenwick-and-segment-trees)
8. [Spatial Data Structures](/algorithms/data-structures/spatial-data-structures)
9. [Skip Lists & Probabilistic Structures](/algorithms/data-structures/skip-lists-and-probabilistic-structures)
10. [B-Trees](/algorithms/data-structures/b-trees)
11. [Data-Stream Algorithms](/algorithms/data-structures/data-stream-algorithms)
12. [Streaming Sketches](/algorithms/data-structures/streaming-sketches)

### 5. Sequences & Strings

1. [Two Pointers & Sliding Windows](/algorithms/sequences/two-pointers-and-windows)
2. [Prefix Sums & Difference Arrays](/algorithms/sequences/prefix-sums)
3. [Monotonic Stacks & Queues](/algorithms/sequences/monotonic-stacks)
4. [Binary Search on the Answer](/algorithms/sequences/binary-search-on-the-answer)
5. [String Matching: Naive & Rabin–Karp](/algorithms/sequences/string-matching)
6. [String Matching: KMP & the Z-Function](/algorithms/sequences/kmp-and-z-function)
7. [Tries & Prefix Trees](/algorithms/sequences/tries)
8. [Suffix Arrays, LCP & Aho–Corasick](/algorithms/sequences/suffix-arrays-and-aho-corasick)

### 6. Graphs

1. [Graph Representations and Traversal](/algorithms/graphs/representations-and-traversal)
2. [Depth-First Search](/algorithms/graphs/depth-first-search)
3. [Topological Sort and Strong Connectivity](/algorithms/graphs/topological-sort-and-scc)
4. [Minimum Spanning Trees](/algorithms/graphs/minimum-spanning-trees)
5. [Kruskal and Prim](/algorithms/graphs/kruskal-and-prim)
6. [Shortest Paths](/algorithms/graphs/shortest-paths)
7. [All-Pairs and Negative Weights](/algorithms/graphs/all-pairs-and-negative-weights)
8. [Network Flow](/algorithms/graphs/network-flow)
9. [Max-Flow Min-Cut and Applications](/algorithms/graphs/max-flow-min-cut)
10. [Bridges & Articulation Points](/algorithms/graphs/bridges-and-articulation-points)
11. [Lowest Common Ancestor & Binary Lifting](/algorithms/graphs/lowest-common-ancestor)
12. [2-SAT via Implication Graphs](/algorithms/graphs/two-sat)
13. [Eulerian Tours](/algorithms/graphs/eulerian-tours)
14. [Bipartite Matching](/algorithms/graphs/bipartite-matching)

### 7. Greedy Algorithms

1. [The Greedy Method](/algorithms/greedy/the-greedy-method)
2. [Scheduling & Interval Partitioning](/algorithms/greedy/scheduling-and-intervals)
3. [Huffman Codes](/algorithms/greedy/huffman-codes)
4. [Matroids & Exchange Arguments](/algorithms/greedy/matroids)
5. [Stable Matching (Gale–Shapley)](/algorithms/greedy/stable-matching)

### 8. Dynamic Programming

1. [Principles of Dynamic Programming](/algorithms/dynamic-programming/principles)
2. [Sequence Alignment & LCS](/algorithms/dynamic-programming/sequence-dp)
3. [Longest Increasing Subsequence](/algorithms/dynamic-programming/longest-increasing-subsequence)
4. [Knapsack & Subset Problems](/algorithms/dynamic-programming/knapsack)
5. [Coin Change & Unbounded Knapsack](/algorithms/dynamic-programming/coin-change-and-unbounded)
6. [Interval DP](/algorithms/dynamic-programming/interval-dp)
7. [Dynamic Programming on Trees](/algorithms/dynamic-programming/tree-dp)
8. [Bitmask DP](/algorithms/dynamic-programming/bitmask-dp)
9. [DP Optimizations](/algorithms/dynamic-programming/dp-optimizations)
10. [Dynamic Programming on Graphs](/algorithms/dynamic-programming/dp-on-graphs)
11. [Digit & Probability DP](/algorithms/dynamic-programming/digit-and-probability-dp)

### 9. Backtracking & Search

1. [Backtracking: Subsets, Permutations & Combinations](/algorithms/backtracking/backtracking-fundamentals)
2. [Constraint Search: N-Queens & Sudoku](/algorithms/backtracking/constraint-search)
3. [Branch & Bound and Meet in the Middle](/algorithms/backtracking/branch-and-bound)
4. [Graph Backtracking: m-Coloring & Hamiltonian Paths](/algorithms/backtracking/graph-backtracking)

### 10. Mathematical Algorithms

1. [Number Theory: GCD & Modular Arithmetic](/algorithms/mathematical-algorithms/number-theory-basics)
2. [Modular Exponentiation & Primality](/algorithms/mathematical-algorithms/modular-exponentiation-and-primality)
3. [Sieves & Factorization](/algorithms/mathematical-algorithms/sieve-and-factorization)
4. [Combinatorics & Counting](/algorithms/mathematical-algorithms/combinatorics)
5. [Matrix Exponentiation](/algorithms/mathematical-algorithms/matrix-exponentiation)
6. [Fast Fourier Transform](/algorithms/mathematical-algorithms/fast-fourier-transform)
7. [Numerical Optimization and Gradient Descent](/algorithms/mathematical-algorithms/gradient-descent)

### 11. Computational Geometry

1. [Geometric Primitives & Orientation](/algorithms/computational-geometry/geometric-primitives)
2. [Convex Hull](/algorithms/computational-geometry/convex-hull)
3. [Sweep-Line Algorithms](/algorithms/computational-geometry/sweep-line)
4. [Polygons & Proximity](/algorithms/computational-geometry/polygons-and-proximity)

### 12. Intractability

1. [P, NP, and Reductions](/algorithms/intractability/p-np-reductions)
2. [NP-Completeness](/algorithms/intractability/np-completeness)
3. [Coping with NP-Hardness](/algorithms/intractability/coping-with-hardness)
4. [Approximation Algorithms](/algorithms/intractability/approximation-algorithms)