Classic algorithms and data structures — from Sedgewick and Cormen, explained in depth.
A general recursive search technique for enumerating every valid configuration of a combinatorial problem — choose an option, recurse, undo the choice — with pruning that abandons a branch the instant it's provably invalid instead of building it out and checking afterward.
A stack kept strictly increasing or decreasing by popping violators before every push — turns "nearest larger/smaller element" from an O(n²) backward scan per element into O(n) total, using the exact aggregate-analysis argument CLRS proves for a stack with a MULTIPOP operation.
Maintaining a contiguous window over an array or string with two forward-only pointers — expanding to absorb new elements, contracting to drop invalid ones — turns a recompute-every-window scan into a single O(n) amortized pass, via the same aggregate-analysis argument that makes ArrayList.add O(1) amortized.
Two indices walking a structure instead of one — converging from opposite ends on sorted input, or moving at different speeds to detect cycles and find midpoints — turning an O(n²) nested scan into a single O(n) pass, proved correct by an exchange argument specific to each problem.
Recursion is a function defined in terms of itself via a base case and a recursive step; the shape of the resulting recurrence — subtracting a constant from n versus dividing n — is what decides whether the running time is linear, exponential, or logarithmic, as concretely shown by factorial, naive Fibonacci, Towers of Hanoi, and binary search. This is the prerequisite the sibling algorithm-analysis-order-of-growth and dynamic-programming-fundamentals concepts both build on without re-deriving.
A non-comparison sort that scatters n keys — assumed uniformly distributed over a known interval [0, K) — into n equal-width buckets, sorts each bucket individually, and concatenates them; under uniformity each bucket holds O(1) elements on average, giving expected O(n) time, a different structural assumption from the sibling counting-sort (bounded integer range) and radix-sort (fixed-width keys) concepts.
Branch and Bound solves integer and combinatorial optimization problems exactly by organizing the search space as a tree of subproblems, using each subproblem's LP-relaxation value as an upper bound to prune entire branches that cannot beat the best integer solution found so far. Traced by hand on a real 2-variable integer program (root relaxation, one infeasible branch, one bound-pruned integer solution, and the branch that becomes the final incumbent) to make the pruning concrete rather than abstract.
The tabular simplex method — turning inequality constraints into a starting dictionary via slack/surplus/artificial variables, reading solutions directly off a tableau, and pivoting via Gauss-Jordan elimination until optimal — picking up exactly where the sibling linear-programming-formulation-and-duality concept deliberately stopped short of the algorithm itself; also covers non-standard forms (minimization, >=/= constraints via the two-phase method) and the dual-simplex/generalized-simplex variants built on the same tableau machinery.
A Bloom filter answers "could this key be in the set?" using a fixed-size bit array and k independent hash functions instead of storing any keys, guaranteeing zero false negatives while accepting a small, precisely tunable false-positive rate — trading exactness for O(k) lookups and O(m) space that never depends on key size or type.
A sorted linked list augmented with randomized "express lane" levels, where each element is independently promoted to level i+1 with probability 1/d; unlike AVL/red-black trees, which guarantee O(log n) height via deterministic rotations/recoloring, a skip list gets O(log n) expected time from randomness alone, with no rebalancing logic at all.
AVL trees are the first self-balancing binary search tree ever published (1962), fixing a plain BST's worst weakness — height, and every operation's cost, depending on insertion order and degrading to O(n) — by capping every node's balance factor at {-1, 0, 1} and restoring it via single or double rotations after each insert/delete, guaranteeing O(log n) height unconditionally.
The exact algorithm for subset sum builds the list of every achievable subset sum and is exponential because that list can double each iteration; trimming it — discarding any value another surviving value already approximates within a factor of 1 + ε/2n — collapses it to polynomial length and turns the algorithm into a fully polynomial-time approximation scheme whose running time is polynomial in both the input size and 1/ε.
GREEDY-SET-COVER repeatedly takes whichever set covers the most still-uncovered elements, giving a logarithmic rather than constant approximation ratio; Section 35.4 then adds two more techniques — a randomized 8/7-approximation for MAX-3-CNF that is pure coin-flipping, and a 2-approximation for weighted vertex cover obtained by relaxing a 0-1 integer program into a linear program and rounding the fractional answer at 1/2.
How to model a problem as a linear program in standard form — shortest paths, max-flow, minimum-cost flow, and multicommodity flow — why an optimal solution always sits at a vertex of the feasible region, and how duality turns a maximization LP into a minimization LP whose matching objective value certifies optimality.
Why multiplying polynomials in coefficient form costs Θ(n²) but only Θ(n) in point-value form, and how the FFT's even/odd divide-and-conquer split over the complex roots of unity makes converting between the two representations — and therefore the whole multiplication — Θ(n lg n).
How M-augmenting paths and symmetric difference solve maximum bipartite matching directly — no max-flow reduction — with Hopcroft-Karp reaching O(√V·E), and how adding edge weights turns it into the assignment problem, which the Hungarian algorithm solves by repeatedly relabeling vertices so that some perfect matching appears inside an equality subgraph.
How new problems are actually proven NP-complete: Lemma 34.8's four-step recipe for reducing from a single known NP-complete language instead of all of NP, then the worked catalog of reductions building CIRCUIT-SAT down through SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP, and SUBSET-SUM — plus the gadget technique and the reduction strategies and pitfalls that generalize.
How to evaluate an algorithm that must commit before seeing the rest of its input — the competitive ratio, defined against an algorithm that knows the future, applied to the elevator-versus-stairs decision, the 4-competitive MOVE-TO-FRONT list heuristic, and online caching, where LRU and FIFO are Theta(k), LIFO and LFU are unbounded, every deterministic policy is stuck at Omega(k), and RANDOMIZED-MARKING reaches O(lg k) against an oblivious adversary.
The greedy algorithm that builds an optimal prefix-free binary code by repeatedly merging the two least-frequent symbols into a trie, proven optimal via an exchange argument and optimal substructure.
Covers APPROX-VERTEX-COVER, a polynomial-time 2-approximation for the NP-complete vertex-cover problem, and APPROX-TSP-TOUR, a 2-approximation for the traveling-salesperson problem under the triangle inequality, plus why no constant-ratio approximation exists without it.
A general iterative method for finding a local minimum of a continuous function by repeatedly stepping opposite the gradient, with a provable convergence bound on convex functions that trades exact answers (like Gaussian elimination's Theta(n^3)) for a faster approximate one.
K-means clustering is NP-hard, so Lloyd's procedure settles for a provably-terminating local-search heuristic — alternately assigning points to their nearest center and recomputing each center as its cluster's centroid — until the assignment stops changing.
Given a complete bipartite graph where every vertex ranks the vertices on the other side, the Gale-Shapley algorithm always finds a matching with no blocking pair — and provably gives every proposer their best achievable partner across all stable matchings, at the cost of giving every proposed-to vertex their worst.
CLRS's second worked dynamic-programming example: find the parenthesization of a chain of matrices that minimizes total scalar multiplications, filling a Theta(n^2) table of subproblems indexed by matrix range in O(n^3) time rather than enumerating the exponentially many possible parenthesizations.
How Sedgewick and Wayne turn a regular expression into a nondeterministic finite-state automaton and simulate it by tracking the entire set of reachable states rather than backtracking, guaranteeing O(NM) worst-case matching time — a stronger guarantee than the backtracking approach java.util.regex.Pattern actually uses.
Counting sort assumes every input element is a nonnegative integer in a bounded range 0 to k, and sorts in Theta(n + k) time — Theta(n) when k = O(n) — by counting and prefix-summing rather than comparing, which is exactly how it beats the Omega(n lg n) bound that applies only to comparison sorts.
The formal cost-analysis framework behind fork-join parallelism: model a computation as a DAG of strands, measure its work (T1) and span (T∞), and use the work law and span law to derive the provable ceiling TP >= max(T1/P, T∞) on how much speedup adding processors can ever buy.
Euclid's algorithm for the GCD and its extended form for computing Bezout coefficients and modular multiplicative inverses, the congruence properties that keep modular arithmetic bounded, and modular exponentiation via repeated squaring — the O(β) recursion, versus a naive O(2^β), that both RSA and Diffie-Hellman run to raise large numbers to large powers mod a large prime.
B-trees are search trees purpose-built for disk-backed storage: fat, sorted nodes and a proactive split-on-the-way-down insertion keep the tree's height tiny relative to a binary search tree, minimizing the number of expensive disk accesses per operation.
How to find the k-th smallest element of an unsorted array in expected linear time by reusing quicksort's own partition step and recursing into only the one side that contains the target rank, plus Cormen's median-of-medians algorithm that guarantees O(n) even in the worst case.
Learn to prove a rigorous worst-case bound on an operation's average cost across any sequence of operations, even when a single operation is expensive — the aggregate, accounting, and potential methods used to justify claims like ArrayList.add being O(1) amortized, and why amortized is a stronger, different guarantee than average-case.
The algorithmic theory behind hash tables: how a hash function maps keys to array indices, why collisions are mathematically unavoidable, and how separate chaining and open addressing/linear probing resolve them under a bounded load factor — plus hash function design (division method, universal hashing) and why deletion is tricky in open addressing.
Solve all-pairs shortest paths in O(V^2 lg V + VE) time by reweighting every edge to be nonnegative via one auxiliary Bellman-Ford run, then running Dijkstra once from every vertex — a composition that beats Floyd-Warshall's O(V^3) on sparse graphs.
A hashing-based substring search: fingerprint the pattern once, then slide a window across the text updating its hash in O(1) per step via a rolling-hash recurrence, falling back to character comparison only on a hash match — covers the collision subtlety, the Las Vegas/Monte Carlo correctness trade-off, and the multi-pattern plagiarism-detection use case KMP and Boyer-Moore don't generalize to as naturally.
How scanning the pattern right to left and precomputing a mismatched-character skip table lets Boyer-Moore slide past several text characters on a single mismatch — often sublinear in practice (~N/M compares per Sedgewick and Wayne's Property O) — at the cost of KMP's unconditional O(N+M) worst-case guarantee.
Compares the three elementary array sorts that ground the rest of this module: selection sort (minimal data movement but blind to input order), insertion sort (adaptive to nearly-sorted input, and CLRS's own running example for loop-invariant correctness proofs), and shellsort (insertion sort extended with a shrinking gap sequence, with a worst-case complexity that's still an open problem for many practical gap sequences).
What P, NP, and NP-completeness precisely mean — the verification-vs-solving asymmetry, why a fast algorithm for one NP-complete problem would solve all of NP, and how to recognize an NP-hard problem in disguise so you reach for approximation, heuristics, or a tractable special case instead.
How Ford-Fulkerson finds the maximum flow through a capacitated network by repeatedly pushing flow along augmenting paths in a residual graph, and why the max-flow min-cut theorem guarantees the algorithm's stopping point is provably optimal.
Compute the minimum number of insert, delete, and substitute operations to transform one string into another using a 2D DP table that extends the LCS table-filling technique with a third predecessor cell for substitution, then backtrack through the table to recover the actual edit sequence.
Contrasts the fractional knapsack problem, which has the greedy-choice property and is solved by a single O(n log n) sort-and-take-greedily pass, with the 0-1 knapsack problem, where the identical-looking greedy rule provably fails (reproducing CLRS's own $220-vs-$160 counterexample) despite both problems sharing optimal substructure — then works out the 0-1 DP recurrence, a hand-verified table, and the O(nW) pseudo-polynomial running time that CLRS leaves as an exercise rather than solving in its main text.
Understand strongly connected components (SCCs) -- the directed-graph generalization of the sibling DFS concept's single-pass undirected connected components, needed because directed reachability is asymmetric. Covers the graph transpose and why it preserves SCCs, Kosaraju's algorithm (DFS on the reverse graph to get reverse postorder, then DFS on the original graph in that order, with each resulting DFS tree exactly one SCC), a hand-verified two-cycle example traced with the graph viz engine, why the algorithm is correct, and its O(V+E) running time.
Learn the all-pairs shortest-paths problem and the Floyd-Warshall dynamic-programming algorithm that solves it in Θ(V³) time by restricting each shortest path's intermediate vertices to a growing set {1, ..., k}, rather than repeating a single-source algorithm once per vertex.
Bellman-Ford solves the fully general single-source shortest-path problem — any graph, any mix of positive and negative edge weights — by relaxing every edge V-1 times instead of relying on Dijkstra's priority-queue ordering, and gets negative-cycle detection for free with one extra relaxation pass.
On a directed acyclic graph, relaxing every vertex's outgoing edges once in topological order finds shortest paths in O(V + E) — faster than Dijkstra's priority queue and correct even with negative edge weights, since a DAG can never contain the negative cycle that would make shortest paths ill-defined.
Order the vertices of a directed acyclic graph so every edge points forward, by running DFS and reading vertices off in reverse order of finish time -- the same O(V+E) traversal the sibling DFS concept already builds, with one push per vertex added.
Dijkstra's algorithm finds shortest paths in a weighted graph with non-negative edges by replacing BFS's FIFO queue with a priority queue ordered by cumulative distance, repeatedly finalizing the closest unprocessed vertex via edge relaxation.
How Prim's and Kruskal's algorithms both exploit the cut property to greedily build a minimum spanning tree -- Prim's growing one tree via a priority queue, Kruskal's sorting all edges and using union-find to skip cycle-closing ones -- traced on a hand-verified 6-vertex example and contrasted for dense vs. sparse graphs.
Understand depth-first search (DFS): a graph traversal that pushes as deep as possible along one branch before backtracking, typically using the recursive call stack itself instead of BFS's explicit queue. Covers the recursive formulation, finding connected components via repeated DFS, discovery/finish-time timestamping and the parenthesis structure, and edge classification (tree, back, forward, cross) — including how back edges reveal cycles and how reverse finish-time order underlies topological sort.
How a binary heap packs a complete binary tree into a plain array with no pointers, using swim/sink to maintain heap order in O(log n), and how that same array-based heap powers heapsort — an in-place sort with a guaranteed O(n log n) worst case.
Traces the union-find data structure through quick-find, quick-union, weighted quick-union, and path compression — the classic dynamic-connectivity problem solved with progressively faster array-backed forests, ending at amortized O(α(n)), effectively constant time in practice.
Solves the activity-selection problem (scheduling the maximum number of non-overlapping activities on a shared resource) with the greedy earliest-finish-time rule, proves why that specific rule is optimal, and shows a verified counterexample where a plausible-sounding alternative rule (shortest duration first) fails — contrasted with the dynamic-programming formulation of the same problem.
How to derive the c[i][j] recurrence for LCS by comparing two sequences' last characters, fill the resulting 2D table bottom-up in O(mn) time, and trace a path backward through the finished table to reconstruct the actual subsequence, not just its length.
See why dynamic programming beats plain recursion only when subproblems overlap, using CLRS's rod-cutting problem: the naive exponential CUT-ROD recursion, the memoized cache that makes each subproblem size computed exactly once, the bottom-up table fill that builds the same answer iteratively, and the two hallmarks — optimal substructure and overlapping subproblems — that determine whether DP applies at all.
How brute-force substring search's O(NM) worst case on self-repetitive input motivates Knuth-Morris-Pratt's key insight: a mismatch already tells you enough about the text to build a small automaton from the pattern and scan the text once, with no backup, in O(N).
A trie stores string keys implicitly as the path from root to node, giving search/insert cost proportional to key length rather than key count (unlike a BST, whose cost depends on N via tree height); the ternary search trie (TST) trims the R-way trie space cost by using 3 links per node instead of an R-slot array, and both structures uniquely support prefix queries such as autocomplete and longest-prefix matching.
Explains LSD and MSD radix sort, two character-indexed string-sorting methods built on key-indexed counting that achieve linear time by sidestepping comparisons entirely, plus the insertion-sort cutoff and 3-way radix quicksort as its large-alphabet alternative.
How BFS visits vertices in order of distance from a source using a queue instead of DFS's stack, guaranteeing shortest paths in an unweighted graph, traced against Sedgewick's own worked example graph.
The five red-black properties, CLRS's insert-fixup cases (recolor and rotate) traced by hand and verified, and why TreeMap/TreeSet use this instead of a plain BST.
The binary-search-tree property, recursive get/put from both books, why every operation costs O(height) rather than automatically O(log n), and why TreeMap/TreeSet use self-balancing red-black trees instead of a plain BST.
How mergesort recursively splits and merges to guarantee O(n log n) in every case (unlike quicksort's O(n²) worst case), Sedgewick's auxiliary-array merge vs. Cormen's sentinel-based merge, and why Java's TimSort is mergesort's real-world descendant.
How repeatedly halving a sorted array's search range finds a target in O(log n) comparisons, Sedgewick's overflow-safe midpoint formula, and CLRS's loop-invariant correctness argument.
How quicksort sorts in-place by partitioning around a pivot, why average-case performance is O(n log n) but worst-case is O(n²), and how Sedgewick's two-pointer partition differs from Cormen's Lomuto scheme.
How to describe an algorithm's running time independent of hardware and input size, using Sedgewick's tilde/order-of-growth shorthand and Cormen's formal O/Ω/Θ bounds.