38 docs tagged with "algorithms"

Capacity-indexed dynamic programming and the direction of one-dimensional updates.

Maximum-cardinality interval scheduling by earliest finish time.

A map for analyzing algorithms, recognizing design patterns, and choosing an appropriate problem-solving family.

Depth-first search over decisions with reversible state and sound pruning.

Single-source shortest paths with negative edges and reachable negative-cycle detection.

Boundary search over sorted random-access data or monotone predicates.

Layered graph traversal and shortest paths by edge count.

Adjacent-swap sorting, its invariant, and its narrow practical role.

Define the objects being counted, then use bijections, double counting, inclusion–exclusion, and pigeonhole arguments to solve finite problems and bound search and output costs.

Stack-based graph traversal, parent structure, and DFS-specific guarantees.

Single-source shortest paths with nonnegative edge weights.

Independent recursive subproblems, combine costs, and recurrence-based analysis.

A state-first method for problems with reusable subproblem structure.

A small recurrence illustrating repeated subproblems and state compression.

Dynamic programming for all-pairs shortest paths and negative-cycle detection.

Density-ordered selection when items are continuously divisible.

A problem-first map for traversal, shortest paths, and minimum spanning trees.

Local-choice algorithms organized around proof obligations and counterexamples.

In-place sorting with a binary heap and a worst-case n-log-n bound.

Optimal binary prefix codes for known symbol frequencies.

Adaptive stable sorting for small or nearly ordered ranges.

Minimum spanning forests by sorted edges and disjoint-set union.

Sequential lookup without ordering or preprocessing assumptions.

Sequence-alignment dynamic programming with length and reconstruction trade-offs.

Stable divide-and-conquer sorting with predictable runtime and linear array workspace.

The cut property connecting Prim's and Kruskal's safe edge choices.

Position-based enumeration with duplicate-value symmetry pruning.

Growing a minimum spanning tree across the lightest eligible cut edge.

Partition-based sorting, pivot risk, duplicate handling, and stack discipline.

A decision map for lookup, ordered search, and graph traversal.

Minimum-selection sorting with fixed comparison cost and few swaps.

The recurrence view of shortest paths and a bridge to graph-specific algorithms.

A decision map for comparison sorting, stability, adaptiveness, and memory trade-offs.

Peak memory analysis across input, output, auxiliary state, and recursion.

A precise 0/1 subset-sum search and its pruning boundaries.

Asymptotic runtime analysis with explicit input measures, models, and case assumptions.

Profit-maximizing unit jobs scheduled into their latest feasible slots.

How existence proofs, explicit constructions, and practical execution differ in finite games, with the limits of strategy stealing and game-tree pruning.