Clrs

Introduction to Algorithms

When to Use

Use this skill when you need to understand, implement, or analyze an algorithm-intensive problem, choose an algorithmic technique, reason about a sophisticated data structure, or answer a CLRS-style exercise.

CLRS Skill Selection

1. Identify the problem being solved and the CLRS concept it most closely matches.
2. If the user mentions a chapter topic directly, load the matching chapter skill.
3. If the topic is inferred rather than named, map the problem to likely CLRS techniques before choosing a chapter skill.
4. Use chapter skills for chapter-specific facts, examples, theorem details, and common traps.
5. Keep the index skill for shared CLRS answer style and routing; do not store chapter-specific algorithms or theorem catalogs here.

Current chapter skills:

• characterizing-running-times: asymptotic notation, running-time bounds, growth-rate comparisons, and loop-bound reasoning.
• divide-and-conquer: recurrences, recursion trees, substitution, Master theorem, Akra-Bazzi, and divide-and-conquer matrix multiplication.
• elementary-data-structures: dynamic sets, arrays, matrices, stacks, queues, linked lists, sentinels, rooted trees, representation invariants, and pointer/locality tradeoffs.
• elementary-graph-algorithms: graph representations, adjacency lists, adjacency matrices, breadth-first search, depth-first search, topological sorting, strongly connected components, edge classification, reachability, articulation points, bridges, biconnected components, and Euler tours.
• data-structures-for-disjoint-sets: disjoint sets, union-find, linked-list and forest representations, weighted union, union by rank, path compression, connected components, offline minimum, and offline LCA.
• hash-tables: direct addressing, chaining, open addressing, universal hashing, load factors, deletion behavior, probe bounds, and cache-aware dictionary design.
• b-trees: external-memory search trees, disk-block indexes, B-tree height bounds, node splitting, top-down insertion, deletion rebalancing, and 2-3-4 tree join/split reasoning.
• augmenting-data-structures: augmented red-black trees, order-statistic trees, rank/select queries, interval trees, overlap search, maintained metadata, and augmentation theorem preconditions.
• binary-search-trees: ordered dynamic sets, predecessor and successor navigation, BST deletion and transplant, red-black rotations and balancing invariants, and production ordered-container choices.
• dynamic-programming: optimal substructure, overlapping subproblems, memoization, bottom-up tables, reconstruction, rod cutting, matrix-chain multiplication, LCS, optimal BSTs, and DP production tradeoffs.
• amortized-algorithms: aggregate analysis, accounting credits, potential functions, multipop stacks, binary counters, dynamic tables, resizing policies, and amortized-versus-average-case traps.
• greedy-algorithms: greedy-choice property, exchange arguments, activity selection, fractional knapsack, Huffman coding, offline caching, and greedy-versus-DP traps.
• minimun-spanning-trees: minimum spanning trees, safe edges, cut and cycle properties, Kruskal's algorithm, Prim's algorithm, bottleneck trees, second-best trees, and MST update reasoning.
• probabilistic-analysis-and-randomized-algorithms: probabilistic analysis, indicator random variables, randomized algorithms, random permutations, balls-and-bins, birthday paradox, streaks, and online hiring.
• parallel-algorithms: fork-join task parallelism, spawn and sync, serial projections, trace DAGs, work/span analysis, greedy scheduling, slackness, determinacy races, parallel loops, matrix multiplication, parallel merge sort, reductions, scans, stencils, and randomized parallel algorithms.
• linear-programming: linear-programming formulations, standard form, feasibility and boundedness, simplex intuition, graph and flow LPs, duality, weak and strong duality, Farkas certificates, complementary slackness, and integer-LP caveats.
• machine-learning-algorithms: k-means clustering, Lloyd's procedure, multiplicative weights, weighted majority, online expert learning, gradient descent, projected gradient descent, convex optimization, linear regression, and regularization.
• matrix-operations: linear systems, LU and LUP decomposition, pivoting, matrix inversion, symmetric positive-definite matrices, Schur complements, least-squares approximation, normal equations, pseudoinverses, tridiagonal systems, and numerical-stability tradeoffs.
• polynomials-and-fft: polynomial representations, point-value evaluation and interpolation, complex roots of unity, DFT and inverse DFT, FFT, convolution, FFT circuits, and modular exactness caveats.
• string-matching: exact pattern search, valid shifts, Rabin-Karp rolling hashes, string-matching automata, KMP prefix functions, suffix arrays, LCP arrays, longest repeated and common substrings, cyclic rotations, and Burrows-Wheeler transforms.
• shortest-paths: single-source and all-pairs shortest paths, relaxation, negative edges and cycles, Bellman-Ford, DAG paths, Dijkstra, Floyd-Warshall, Johnson, difference constraints, transitive closure, arbitrage, and path reconstruction.
• maximum-flow: flow networks, residual networks, augmenting paths, cuts, Ford-Fulkerson, Edmonds-Karp, min-cut certificates, bipartite matching reductions, vertex capacities, and flow-model transformations.
• matchings-in-biparite-graphs: bipartite matching, augmenting paths, Hopcroft-Karp, stable marriage, Gale-Shapley, Hungarian assignment, feasible labels, equality subgraphs, and matching-specific proof certificates.
• np-completeness: P, NP, co-NP, NP-hardness, NP-completeness, polynomial-time reductions, certificates, CIRCUIT-SAT, SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, HAM-CYCLE, TSP, SUBSET-SUM, encoding, and pseudo-polynomial traps.
• approximation-algorithms: approximation ratios, PTAS and FPTAS distinctions, vertex cover, metric and general TSP, set cover, randomized MAX-3-CNF, LP rounding, subset-sum trimming, and approximation proof certificates.
• online-algorithms: competitive analysis, online/offline comparisons, elevator and ski-rental hedging, move-to-front list update, online caching, randomized marking, and adversary models.
• sorting-and-order-statistics: heaps, priority queues, sorting choice, stability, linear-time sorting preconditions, selection, medians, quantiles, and top-k decisions.

Mathematical Formatting

Always put mathematical expressions in display LaTeX blocks. Do not put formulas in inline code spans, inline math, or plain prose. Notation names such as O-notation, Theta-notation, or little-omega can appear in prose, but any expression, inequality, limit, recurrence, or growth comparison must be displayed as a block.

This applies to the entire response, including headings, scratch work, examples, thresholds, ratios, and explanatory narration. If a sentence would contain symbols such as variables, powers, inequalities, limits, or fractions, split the expression into a display block and refer to it from prose as "the expression above" or "the bound below." Do not leak scratch-work formulas in prose before the polished answer.

Start directly with the polished answer. Do not include planning paragraphs, scratch-work narration, or "I am checking" preambles; those are common places where formulas accidentally escape display blocks.

Never place formulas in Markdown headings. Use prose headings such as "First claim" or "Little-o check," then put the formula below the heading in a display block.

Forbidden patterns:

• A heading that embeds a formula.
• A prose sentence that embeds a ratio, limit, threshold, recurrence, or asymptotic relation.
• An inline code span that contains a formula or inequality.

Safe pattern:

## First claim

The claim is true.

$$
\frac{f(n)}{g(n)} \to 0
$$

Therefore the first expression is little-o of the second expression.

General CLRS Conventions

• State which case, model, or quantity is being analyzed before giving a bound or theorem result.
• Ground answers in CLRS terminology and theorem names when relevant; cite theorem numbers when the chapter skill provides them.
• Check theorem preconditions before applying a named result.
• Prefer precise tight bounds when justified, and say when only an upper or lower bound has been shown.
• Keep chapter-specific worked examples, algorithms, proof recipes, and common mistakes in the relevant chapter skill.