Algorithms

Asymptotic bounds, recurrences, and amortized accounting.

1. Amortized Analysis of Dynamic Arrays
2. Asymptotic Notation as Sets of Functions, Not Growth Rates
3. The Master Theorem and the Recursion Tree Behind Its Three Cases
4. Comparison Lower Bounds From Decision Trees and Adversaries
5. Expected Cost, Amortized Cost, and Where the Average Comes From
6. Space Complexity Accounting for Recursion, Auxiliary Buffers and Output

Comparison sorts, distribution sorts, and order statistics.

1. The Comparison Sorting Lower Bound and What It Actually Counts
2. Insertion Sort and the Inversion Count That Predicts Its Runtime
3. Merge Sort: Why Stability Survives the Merge and What the Buffer Costs
4. Quicksort Partition Schemes and the Duplicate-Key Quadratic
5. Counting and Radix Sort: Choosing the Pass Count and the Digit Width
6. Comparator Contracts and Why a Bad One Crashes the Sort

Trees, hashing, and structures that answer lookup queries.

1. Lower Bound, Upper Bound, and the Invariant That Makes Binary Search Correct
2. Interpolation Search and What Uniform Key Distribution Buys
3. Eytzinger Layout: Storing a Search Tree in Level Order
4. B-Tree Fanout Arithmetic and the Cost of a Point Lookup
5. Extendible Hashing and Why the Directory Doubles
6. Probe Sequences in Open-Addressed Hash Tables

Reachability, connectivity, and traversal order.

1. Adjacency Lists, Matrices, and the Cost of Asking Who Is Adjacent
2. Why Breadth-First Search Cannot Discover Vertices Out of Distance Order
3. Discovery and Finish Times: What DFS Edge Classification Encodes
4. Iterative Depth-First Search Without Losing Finish Times
5. Labelling Connected Components Once Versus Maintaining Them Under Insertions
6. Two-Colouring a Graph: Why BFS Decides Bipartiteness and Odd Cycles Do Not

Path costs, relaxation, and all-pairs methods.

1. Relaxation and the Optimality Condition Behind Shortest-Path Algorithms
2. Dijkstra and the Settled-Set Invariant
3. Bellman-Ford, Round Counts, and Negative-Cycle Detection
4. Priority Queues for Dijkstra: Decrease-Key, Lazy Deletion, and Buckets
5. A* and the Conditions on a Heuristic
6. Bidirectional Search and the Problem of Knowing When to Stop

Optimal substructure, state design, and memoization.

1. Recurrences as DAGs: Why Optimal Substructure Makes Tables Work
2. Memoization Mechanics: Cache Keys, Laziness, and Recursion Depth
3. State Sufficiency: What the Past Must Leave Behind
4. Pseudo-Polynomial Knapsack: Why the Capacity State Is Not Polynomial
5. Edit Distance and the Shape of a Two-Dimensional Table
6. Interval DP: Choosing the Last Operation Instead of the First

Exchange arguments, matroids, and ratio guarantees.

1. The Exchange Argument: Proving a Greedy Choice Is Safe
2. Earliest-Finish-First for Interval Scheduling
3. Huffman Coding and the Greedy Merge
4. Matroid Structure and the Exact Boundary of Greedy Optimality
5. Fractional Relaxation and the Knapsack Integrality Gap
6. Kruskal, the Cut Property, and Why Any Minimum Edge Is Safe

Pattern matching, suffix structures, and text compression.

1. The Prefix Function and Linear-Time Exact Matching
2. Polynomial Rolling Hashes and the Rabin-Karp Trade
3. Right-to-Left Scanning and the Boyer-Moore Shift Tables
4. Aho–Corasick Failure Links and Multi-Pattern Scanning
5. Suffix Arrays, Prefix Doubling, and the Kasai LCP Scan
6. Suffix Automata and Counting Distinct Substrings Online

Convexity, intersections, and spatial queries.

1. Convex Hulls by Monotone Chain
2. Point in Polygon: Crossing Number and Winding Number
3. Detecting Segment Intersections with Orientation Tests
4. Exact Geometric Predicates and Adaptive Precision
5. Bentley–Ottmann: Reporting All Crossings with a Sweep Line
6. Delaunay Triangulation and the Empty Circumcircle Test

Probability in algorithm design and analysis.

1. Unbiased Random Integers from a Finite Random Source
2. Uniform Random Permutations and the Fisher-Yates Shuffle
3. Randomized Quicksort and the Expected Comparison Count
4. Randomized Recurrences and the Indicator Variable Method
5. The Probabilistic Method: Proving That a Good Object Exists
6. Universal Hashing and Guarantees That Hold for Every Input

Sublinear sketches over unbounded input.

1. The Streaming Model: One Pass, Sublinear Space, Approximate Answers
2. Counting Distinct Elements with HyperLogLog Registers
3. Frequency Moments and the Tug-of-War Sketch
4. Count-Min Sketch: Why the Minimum of Overestimates Is the Estimate
5. Heavy Hitters with Misra-Gries Counters and Space-Saving Buckets
6. Reservoir Sampling and Priority Sampling on a Single Pass

Work, span, and concurrency in algorithm design.

1. Work, Span, and the Bound on Parallel Execution Time
2. Reduction Trees and What Associativity Buys
3. Work Stealing: Per-Processor Deques and Why Thieves Take the Oldest Task
4. Parallel Prefix Scan: Hillis-Steele Versus Blelloch
5. Merge-Path Partitioning: Splitting Two Sorted Runs Without Sampling
6. Granularity and the Sequential Cut-Off