82 docs tagged with "algorithms"

Dijkstra's algorithm finds the shortest path to every vertex by always expanding the closest

Everything below this point in the knowledge base is about what the machine can do. This section is

Some structures cannot be made cheap on every single call, but can be made cheap *on average over any

An array is a block of contiguous memory holding equally-sized elements. That one property gives it

Backtracking searches a space of candidate solutions by building them one choice at a time, and

A binary search tree is $O(\log n)$ only while it stays short, and nothing in the plain

Big-O describes an upper bound on growth. Saying an algorithm is $O(n^2)$ claims that beyond some

Binary search compares the target against the middle element of a sorted array and discards half

Every binary search so far has searched an array: a sorted sequence of values sitting in memory,

A graph is bipartite when its vertices split into two groups such that every edge runs between

Bit-manipulation techniques are small, well-known patterns for testing, setting, and transforming

The Boost Graph Library is a generic framework for graph data structures and algorithms. It

Bubble sort repeatedly walks the array comparing adjacent pairs and swapping them when they are out

In almost every situation the correct answer is call your language's built-in sort. Those

"How many ways" questions tempt a direct answer: generate every arrangement, every selection, every

In practice you meet perhaps eight growth classes. Recognising which one a piece of code falls into —

Measuring an algorithm by timing it tells you about your laptop, your compiler, your input, and the

This page is a reference, not a tutorial — each numbered page in this section explains the reasoning

Every comparison sort on this page's siblings is bound below by $Ω(n \log n)$ — a fact proved by a

A cycle is a path that leaves a vertex and, by following edges, returns to it. That definition reads

A data structure is a decision about which operations you want to be cheap. There is no structure

This page is a reference, not a tutorial — each page in this section explains the reasoning behind the

A stack grows and shrinks at one end; a queue adds

Divide and conquer breaks a problem into independent subproblems of the same kind, solves those

Dynamic programming applies when a problem has overlapping subproblems — the same sub-computation

Both of these are binary search wearing a different hat. Exponential search still finds a target in a

Every algorithm on the earlier pages of this folder assumes the whole array fits in memory, so any two

A singly-linked list, or anything shaped like one — a permutation's i -> p[i] mapping, a

The greatest common divisor looks like a problem for factoring both numbers and comparing their

Once a problem is expressed as a graph, a small set of algorithms

This page is a reference, not a tutorial — see Graph Algorithms Overview for a first

A graph is a set of vertices and a set of edges connecting them. That is nearly no structure

A greedy algorithm makes the choice that looks best right now and never reconsiders it. When that

A hash table turns a key into an array index by running it through a hash function, then reads or

A priority queue answers one question: what is the most important item right now? A binary

Heapsort is selection sort with a better way of selecting. Selection sort scans

Insertion sort builds the sorted result one element at a time, taking the next element and sliding it

A calendar full of meetings, a set of (start, end) ranges to merge, a question like "how many

Iterators are the glue between containers and algorithms. They provide a uniform interface for traversing and accessing elements in different container types, enabling generic algorithms.

The naive substring scan tries the pattern at every text position and, on a mismatch, throws away

Linear search examines each element in turn until it finds what it is looking for or runs out. It is

A linked list stores each element in its own node, together with a pointer to the next one. Nothing

A cache with unlimited capacity is just a hash table. The interesting problem

Every algorithm folder so far has assumed arithmetic just works: a hash function combines numbers,

Mergesort splits the array in half, sorts each half recursively, and merges the two sorted halves

Given a connected, undirected, weighted graph, a spanning tree picks exactly V - 1 edges that keep

"For each element, find the nearest element to the right that is bigger" looks like it needs a nested

The obvious way to find a pattern of length m inside a text of length n is to try it at every

A flow network is a directed graph where every edge has a capacity, one vertex is a source pumping

Most complexity analysis on this site asks how fast a known algorithm runs. This page asks a

Almost every GPU kernel, however specialized, is built from a small set of recurring data-access shapes. Recognizing which pattern a problem is — before writing any code — tells you how parallelizable it is, what its likely performance limiter will be, and often points directly at a library implementation that already exists and is already tuned. This page names those shapes once, and every later applied-kernel page in this knowledge base assumes you already know these names — "this is a reduction" or "this needs a scan" is meant to carry full meaning by the time you reach folder 13.

Summing a range of an array costs time proportional to the range. Do it once and nobody notices; do it

Testing whether a single number n is prime is a small, self-contained problem: try dividing it by

Every structure so far in this section answers its question exactly, at the cost of storing enough

The named algorithms in the earlier sections are instances of a smaller number of recurring

This page is a reference, not a tutorial — see Problem-Solving Patterns Overview for a

Finding the k-th smallest element does not require sorting the whole array. Sorting throws away no

Quicksort picks an element as the pivot, rearranges the array so that everything smaller sits to

A deterministic algorithm has exactly one worst case, and if that worst case is realistic — an

Ranges (C++20) is a modern library that provides composable, lazy-evaluated operations on sequences. It replaces traditional iterator pairs with range objects and introduces views for efficient data transformation pipelines.

A recursive algorithm's cost is itself defined recursively — mergesort's cost on n elements is twice its

Dynamic Programming names the idea — overlapping subproblems plus

Every algorithm in this folder answers the same question — "is this value present, and where" — but

Prefix sums answer range-sum

Selection sort divides the array into a sorted prefix and an unsorted remainder. Each round it scans

"Shortest" means fewest edges on an unweighted graph and lowest total weight on a weighted one, and

Sorting is the most-studied problem in the field, and not because arranging things in order is

This page is a reference, not a tutorial — each algorithm's own page derives the bound it gets here.

Time complexity answers "how does the work grow?"; space complexity asks the same question about

Stacks and queues are not new storage — they are restrictions on storage. Both hold a sequence,

STL algorithms are generic functions that work with any container through iterators. They provide tested, optimized implementations of common operations. Never write your own sort or search - use the STL!

Every algorithm in this folder assumes a cost model for three operations that look free and are

A string is an array — but three things about it break the assumptions the rest of this section

In a directed graph, two vertices are strongly connected if each can reach the other — a path

Every algorithm earlier in this folder answers one question: does this one pattern occur in this

"Find the k largest" looks like a sorting problem, and sorting solves it — but sorting also computes

A topological sort orders the vertices of a directed acyclic graph so every edge points forward —

Breadth-first and depth-first search both visit every vertex reachable from a start point, in

A tree is a set of nodes where each node has one parent (except the root) and no cycles. That single

A hash set answers "is this exact string in the set?" and nothing else. It cannot answer "what strings

Both patterns replace a nested loop with a single pass by maintaining two indices that only ever move

Some problems never ask what is in a group. They ask only whether two things have ended up in the