Algorithms Dictionary

Terms used in the course, each with a short definition and the chapter where it is explained. The chapter column links to that chapter's lecture notes.

TermDefinitionChapter
A* searchA search algorithm that expands nodes in order of f = g + h and is guided by a heuristic to find a shortest path.6 · Shortest Paths
adaptive (sort)Describes a sorting algorithm that runs faster when the input is already partially sorted.3 · Sorting Algorithms
adjacency listA graph representation that stores a list of neighbors for each vertex, using O(V + E) memory.5 · Graph Traversal
adjacency matrixA graph representation that records the presence (or weight) of each edge in a V × V matrix.5 · Graph Traversal
admissible heuristicA heuristic that never overestimates the true remaining cost to the goal.6 · Shortest Paths
Aho–Corasick algorithmAn algorithm that finds many patterns in a text in a single pass, using a trie of the patterns and failure links.11 · Tries
algorithmA method that solves a problem in a finite number of clearly defined steps.1 · Introduction
algorithm analysisThe study of an algorithm's running time and memory requirements as a function of the input size.1 · Introduction
all-pairs shortest pathsThe shortest paths between every pair of vertices (Floyd-Warshall).6 · Shortest Paths
alphabetThe set of characters that can appear in strings (Σ).9 · String Matching and Compression
amortized analysisFinding the cost per operation by dividing the total cost of a sequence of operations by the number of operations.2 · Algorithm Complexity
ancestorAny node on the path from a given node up to the root of a tree: its parent, its parent's parent, and so on.5 · Graph Traversal
articulation pointA vertex whose removal disconnects a connected undirected graph.5 · Graph Traversal
asymptotic notationThe notations O, Ω and Θ, which describe growth for large n by discarding constant factors and lower-order terms.2 · Algorithm Complexity
augmenting pathA path from the source to the sink in the residual network along which the flow can be increased.8 · Network Flow
autocompleteSuggesting likely words from the prefix typed so far, a typical use of a trie.11 · Tries
auxiliary spaceThe memory an algorithm needs in addition to the memory that holds its input; space complexity is usually stated for this.2 · Algorithm Complexity
average caseThe expected number of operations over a given distribution of inputs.2 · Algorithm Complexity
back edgeIn a DFS, an edge to an ancestor that is still on the stack; it signals a cycle.5 · Graph Traversal
bad character ruleA shifting rule that aligns the mismatched text character with its last occurrence in the pattern.9 · String Matching and Compression
base caseThe smallest case that a recursion solves directly, without calling itself.2 · Algorithm Complexity
Bellman-Ford algorithmAn algorithm that relaxes all edges V − 1 times and allows negative edge weights.6 · Shortest Paths
best caseThe input of a given size that requires the fewest operations.2 · Algorithm Complexity
bidirectional searchA search that runs BFS from the source and from the target at the same time and stops when the two waves meet.6 · Shortest Paths
Big O notationf(n) = O(g(n)): for large enough n, f is bounded above by a constant multiple of g.2 · Algorithm Complexity
Big Omega (Ω)f(n) = Ω(g(n)): for large enough n, f is bounded below by a constant multiple of g.2 · Algorithm Complexity
Big Theta (Θ)f(n) = Θ(g(n)): f is both O(g(n)) and Ω(g(n)), so the two grow at the same rate.2 · Algorithm Complexity
binary searchA search on a sorted array that compares with the middle element and halves the range at each step: O(log n).4 · Searching Algorithms
binary trieA trie over the alphabet {0, 1} that stores keys bit by bit.11 · Tries
bipartite graphA graph whose vertices can be split into two groups so that every edge joins the two groups.5 · Graph Traversal
bipartite matchingA set of edges in a bipartite graph with no common endpoints; it can be found with maximum flow.8 · Network Flow
blocking flowA flow that blocks every path in the level graph by saturating at least one of its edges.8 · Network Flow
Borůvka's algorithmAn MST algorithm that adds the lightest outgoing edge of every component in each round.7 · Minimum Spanning Trees
bottleneckThe smallest residual capacity on an augmenting path, which is the amount of flow added in that round.8 · Network Flow
Boyer-Moore algorithmA search that compares the pattern from right to left and makes large shifts.9 · String Matching and Compression
breadth-first search (BFS)A traversal that visits vertices layer by layer in order of distance from the start, using a queue.5 · Graph Traversal
bridgeAn edge whose removal splits the graph into more components.7 · Minimum Spanning Trees
brute force (naive)An approach that tries every possibility one by one.9 · String Matching and Compression
bubble sortA sort that compares neighboring items and swaps them when out of order; each pass moves the largest item to the end.3 · Sorting Algorithms
bucketEach cell of the array in a hash table.4 · Searching Algorithms
bucket sortA sort that distributes items into buckets by value range and then sorts each bucket.3 · Sorting Algorithms
Burrows–Wheeler transform (BWT)A reversible transform that takes the last column of the sorted rotations of a string and makes compression easier.10 · Advanced String Algorithms
call stackThe stack of frames that holds the parameters, local variables and return address of each method call.2 · Algorithm Complexity
capacityThe largest amount of flow that can pass through an edge.8 · Network Flow
catastrophic backtrackingWhen a backtracking regular-expression engine tries exponentially many alternatives because of nested quantifiers and appears to hang.10 · Advanced String Algorithms
collisionTwo different keys hashing to the same value.4 · Searching Algorithms
comparison sort lower boundEvery comparison-based sort needs Ω(n log n) comparisons in the worst case.3 · Sorting Algorithms
complete graphA graph in which every pair of vertices is joined by an edge; with n vertices it has n(n − 1)/2 edges.5 · Graph Traversal
complexity classA group of algorithms with the same growth rate (constant, logarithmic, linear, and so on).2 · Algorithm Complexity
complexity theoryThe field that studies the resources an algorithm uses, such as time and memory, as a function of the input size.2 · Algorithm Complexity
compressed trie (radix tree)A trie that merges chains of single-child nodes into a single edge.11 · Tries
compressionRepresenting data with fewer bits.9 · String Matching and Compression
compression ratioThe compressed size divided by the original size; the smaller it is, the better the compression.9 · String Matching and Compression
connected componentA maximal set of vertices that are joined to one another by paths.7 · Minimum Spanning Trees
consistent heuristicA heuristic that satisfies h(u) ≤ w(u, v) + h(v) for every edge (u, v) and h(goal) = 0.6 · Shortest Paths
constant timeA running time that does not depend on the input size: O(1).1 · Introduction
correctnessThe property that an algorithm produces the correct output for every valid input.1 · Introduction
counting sortA non-comparison sort that counts small integer keys and places them using prefix sums.3 · Sorting Algorithms
cubicO(n³) growth; for example, straightforward matrix multiplication.1 · Introduction
cut (s-t cut)A split of the vertices into an s side and a t side; its capacity is the sum of the capacities of the edges going from the s side to the t side.8 · Network Flow
cut propertyThe lightest edge crossing a cut belongs to some MST.7 · Minimum Spanning Trees
cycleA closed path that returns to its starting vertex without repeating an edge.5 · Graph Traversal
cycle propertyThe heaviest edge of a cycle (if it is unique) belongs to no MST.7 · Minimum Spanning Trees
decision treeA tree that models a comparison-based algorithm: internal nodes are comparisons and leaves are the resulting orderings.3 · Sorting Algorithms
decrease and conquerAn approach that solves a problem by reducing it to a single smaller subproblem (for example, binary search).4 · Searching Algorithms
definitenessThe property that every step is defined precisely and unambiguously.1 · Introduction
degreeThe number of edges attached to a vertex; in a directed graph, in-degree and out-degree are counted separately.5 · Graph Traversal
depth-first search (DFS)A traversal that goes as deep as possible along one branch and then backtracks (using a stack or recursion).5 · Graph Traversal
deterministic algorithmAn algorithm that follows the same steps and gives the same output every time it runs on the same input.1 · Introduction
deterministic finite automaton (DFA)A finite state machine with exactly one transition for every (state, symbol) pair.10 · Advanced String Algorithms
Dijkstra's algorithmA shortest-path algorithm for non-negative weights that repeatedly picks the vertex with the smallest distance and relaxes its edges.6 · Shortest Paths
Dinic's algorithmA maximum-flow algorithm that finds blocking flows in level graphs: O(V²·E).8 · Network Flow
directed acyclic graph (DAG)A directed graph with no cycles; it plays a special role in task scheduling.5 · Graph Traversal
directed graphA graph whose edges have a direction.5 · Graph Traversal
distanceThe length of a shortest path to a vertex; for strings, a measure of the difference between two strings.6 · Shortest Paths
dynamic arrayAn array that grows by copying its contents into a larger array when it becomes full (for example, Java's ArrayList).2 · Algorithm Complexity
edgeA connection between two vertices; it may be directed and may carry a weight.5 · Graph Traversal
edit distanceThe minimum number of insertions, deletions and substitutions needed to turn one string into another.10 · Advanced String Algorithms
Edmonds-Karp algorithmFord-Fulkerson with augmenting paths chosen by BFS (fewest edges): O(V·E²).8 · Network Flow
effectivenessThe property that every step is basic enough to be carried out in finite time with pencil and paper.1 · Introduction
end-of-word markerA mark on a trie node showing that the path from the root to that node spells a word.11 · Tries
Euclid's algorithmAn algorithm that finds the greatest common divisor of two numbers by repeated division with remainder.1 · Introduction
excess flowThe amount by which the flow entering a vertex exceeds the flow leaving it.8 · Network Flow
exponentialGrowth such as O(2ⁿ), where the running time doubles each time n increases by one.1 · Introduction
exponential searchA method that grows the range as 1, 2, 4, … and then applies binary search.4 · Searching Algorithms
factorialO(n!) growth, such as trying all permutations.1 · Introduction
failure linkIn Aho–Corasick, a link from a node to the node for the longest proper suffix of its string that is present in the trie.11 · Tries
finite state machine (FSM)A model of computation made up of a finite number of states and transitions that depend on the input.10 · Advanced String Algorithms
finitenessThe property that an algorithm terminates after a finite number of steps for every input.1 · Introduction
flow conservationAt every vertex other than the source and the sink, the incoming flow equals the outgoing flow.8 · Network Flow
flow networkA directed graph whose edges have capacities and which carries flow from a source to a sink.8 · Network Flow
Floyd-Warshall algorithmA dynamic-programming algorithm that finds all-pairs shortest paths by adding intermediate vertices one at a time: O(V³).6 · Shortest Paths
Ford-Fulkerson methodA general method that keeps increasing the flow until no augmenting path remains.8 · Network Flow
good suffix ruleA shifting rule based on another occurrence in the pattern of the suffix that has just matched.9 · String Matching and Compression
graphA structure made of vertices and the edges that connect them: G = (V, E).5 · Graph Traversal
graph traversalSystematically visiting all reachable vertices of a graph.5 · Graph Traversal
greedy best-first searchA search that looks only at the estimated remaining cost to the goal; it rushes toward the goal but ignores the cost of the path so far.6 · Shortest Paths
growth rateHow fast a function grows as n grows; the basis for comparing algorithms.2 · Algorithm Complexity
hash functionA function that maps a key to a table index.4 · Searching Algorithms
hash tableA table that stores keys at positions given by a hash function, with O(1) search on average.4 · Searching Algorithms
heapA complete binary tree in which every node is greater than its children (max-heap) or smaller than its children (min-heap).3 · Sorting Algorithms
heap sortA sort that builds a max-heap from the array and then repeatedly moves the root to the end.3 · Sorting Algorithms
heuristicA rule or function that gives a good result or estimate without any guarantee of exactness.6 · Shortest Paths
in-placeUsing only O(1) (or very little) extra memory besides the input.3 · Sorting Algorithms
inputThe values, drawn from a specified set, that an algorithm receives at the start.1 · Introduction
input sizeThe value n that measures the size of a problem (array length, number of vertices, and so on).1 · Introduction
insertion sortA sort that inserts each item into its correct place in the sorted part.3 · Sorting Algorithms
interpolation searchA search that estimates the position of the target from the end values; O(log log n) on uniformly distributed data.4 · Searching Algorithms
inversionA pair of indices with i < j and a[i] > a[j].3 · Sorting Algorithms
iterated logarithmlog* n: the number of times log₂ must be applied to n before the result is 1 or less.2 · Algorithm Complexity
iterative deepening DFS (IDDFS)A series of DFS runs with the depth limit raised to 0, 1, 2, and so on; it combines DFS's small memory use with BFS's guarantee of finding the shallowest solution.5 · Graph Traversal
jump searchA method that jumps ahead in steps of √n in a sorted array and then searches linearly within the block.4 · Searching Algorithms
Knuth-Morris-Pratt (KMP)An algorithm that searches in O(n + m) without moving backward in the text, using the LPS table.9 · String Matching and Compression
Kruskal's algorithmAn MST algorithm that scans edges in order of weight and adds those that do not form a cycle.7 · Minimum Spanning Trees
Lempel-Ziv-Welch (LZW)A compression method that adds seen strings to a dictionary and encodes them as dictionary indices.9 · String Matching and Compression
level graphThe subgraph made of the edges that go from one BFS level to the next.8 · Network Flow
Levenshtein distanceThe edit distance in which each insertion, deletion and substitution costs 1.10 · Advanced String Algorithms
lexicographic orderComparing strings character by character in alphabetical order.10 · Advanced String Algorithms
linearGrowing in proportion to n: O(n).1 · Introduction
linear probingResolving a collision by searching for the next empty cell and placing the key there.4 · Searching Algorithms
linear searchA search that examines the items one by one from the beginning: O(n).4 · Searching Algorithms
linearithmicO(n log n) growth; the class of efficient comparison-based sorts.2 · Algorithm Complexity
load factorThe ratio of the number of keys in the table to the number of cells (α = n/m).4 · Searching Algorithms
logarithmicGrowing in proportion to log n; for example, binary search.4 · Searching Algorithms
longest common prefixThe longest beginning shared by all strings in a set of strings.11 · Tries
longest prefix matchChoosing the longest of the prefixes that match an address; the basic rule of IP routing.11 · Tries
lookahead / lookbehindA regular-expression construct that tests whether the text to the right or left matches a pattern without advancing the position.10 · Advanced String Algorithms
loop invariantA statement that is true at the start of every iteration of a loop and is used to show that an algorithm is correct.3 · Sorting Algorithms
lossless / lossy compressionWith lossless compression the decompressed data is bit-for-bit identical to the original; with lossy compression perceptually unimportant detail is discarded and the result is only close to the original.9 · String Matching and Compression
lower boundA limit that a value cannot go below; Ω notation gives a lower bound.2 · Algorithm Complexity
LPS tableFor each position, the length of the longest proper prefix that is also a suffix.9 · String Matching and Compression
LSD / MSD radix sortRadix sort that starts from the least significant digit (right) or the most significant digit (left).3 · Sorting Algorithms
master theoremA rule that solves recurrences of the form T(n) = aT(n/b) + f(n) in three cases.2 · Algorithm Complexity
max-flow min-cut theoremThe value of a maximum flow equals the capacity of a minimum cut.8 · Network Flow
maximum flowThe largest total flow that can be sent from the source to the sink.8 · Network Flow
median-of-threeA rule that picks the median of the first, middle and last items as the pivot.3 · Sorting Algorithms
mergeThe operation that combines two sorted arrays into one sorted array.3 · Sorting Algorithms
merge sortA sort that splits the array in half, sorts each half and then merges the sorted halves.3 · Sorting Algorithms
minimum spanning forestA minimum spanning tree for each component of a graph that is not connected.7 · Minimum Spanning Trees
minimum spanning tree (MST)A spanning tree with the smallest possible total edge weight.7 · Minimum Spanning Trees
negative cycleA cycle whose weights add up to a negative number; if one exists, shortest paths are undefined.6 · Shortest Paths
nondeterministic finite automaton (NFA)A finite state machine that allows zero, one or several transitions for a (state, symbol) pair.10 · Advanced String Algorithms
open addressingA hashing method in which a colliding key is placed in another empty cell of the table.4 · Searching Algorithms
outputThe result an algorithm produces, which has a specified relationship to the input.1 · Introduction
parentThe node directly above a node in a tree; BFS and DFS trees, Prim's algorithm and union-find store it in a parent array.5 · Graph Traversal
partitionSplitting an array into items smaller than the pivot and items larger than it (Lomuto, Hoare).3 · Sorting Algorithms
pathA sequence of vertices obtained by moving along one edge at a time from vertex to neighbor; its length is the number of edges it contains.5 · Graph Traversal
path compressionLinking the nodes visited during a find operation directly to the root.7 · Minimum Spanning Trees
patternThe string being searched for in the text (P).9 · String Matching and Compression
prefixA part taken from the beginning of a string.9 · String Matching and Compression
prefix doublingBuilding a suffix array by doubling the length of the sorted prefixes in each round.10 · Advanced String Algorithms
prefix functionIn KMP, a table that depends only on the pattern and gives the shift for each possible match length; another name for the LPS table, also written π.9 · String Matching and Compression
prefix queryFinding all keys that start with a given prefix.11 · Tries
preflowA flow that respects the capacity constraints but allows excess flow at vertices other than the source instead of conservation; push-relabel works with it.8 · Network Flow
Prim's algorithmAn MST algorithm that grows a tree from one vertex by adding the lightest outgoing edge.7 · Minimum Spanning Trees
primary clusteringIn linear probing, the tendency of occupied cells to form long consecutive blocks.4 · Searching Algorithms
priority queueA structure that quickly returns the item with the smallest (or largest) key, usually implemented with a heap.6 · Shortest Paths
probeThe operation of looking at an array cell and comparing it with the value being searched for.4 · Searching Algorithms
proper prefixA prefix that is not equal to the string itself; likewise, a proper suffix is a suffix not equal to the string itself.9 · String Matching and Compression
pseudocodeA way of describing an algorithm step by step without depending on a programming language.5 · Graph Traversal
push-relabelA method that finds a maximum flow by pushing excess flow at vertices according to their heights.8 · Network Flow
quadraticO(n²) growth; typically two nested loops.3 · Sorting Algorithms
quantifierAn element of a regular expression (*, +, ?, {m,n}) that says how many times an item may repeat.10 · Advanced String Algorithms
quick sortAn algorithm that partitions around a pivot and sorts both sides recursively.3 · Sorting Algorithms
Rabin-Karp algorithmA search algorithm that compares the hash values of windows.9 · String Matching and Compression
radix sortA method that sorts keys digit by digit using a stable sort (LSD, MSD).3 · Sorting Algorithms
random-access machine (RAM)An abstract model of computation in which every basic operation and every memory access takes one unit of time.2 · Algorithm Complexity
recurrence (relation)An equation that defines T(n) in terms of the values of T on smaller inputs.2 · Algorithm Complexity
recursionA function calling itself to solve a smaller instance of the problem.2 · Algorithm Complexity
recursion treeA tree that shows the recursive calls and the work done at each level; used to solve recurrences.2 · Algorithm Complexity
reference (child pointer)A link from a node to one of its children.11 · Tries
regular expressionA formal expression that describes a set of strings (a search pattern).10 · Advanced String Algorithms
regularity conditionThe condition a · f(n/b) ≤ k · f(n) (k < 1) required for case 3 of the master theorem.2 · Algorithm Complexity
relaxationIf d[u] + w(u, v) < d[v], updating the distance estimate and the parent of v.6 · Shortest Paths
residual capacityThe amount of flow that can still be sent through an edge: c − f.8 · Network Flow
residual networkA network that shows the remaining capacity on each edge and the flow that can be undone (the reverse edge).8 · Network Flow
reverse-delete algorithmAn MST algorithm that examines edges from heaviest to lightest and deletes those whose removal does not disconnect the graph.7 · Minimum Spanning Trees
rolling hashA hash that can be updated in O(1) when the window slides by one position.9 · String Matching and Compression
run-length encoding (RLE)A compression method that writes consecutive repeats as (value, count) pairs.9 · String Matching and Compression
running timeThe number of basic operations an algorithm performs, or the time it takes, on a particular input.2 · Algorithm Complexity
saturated edgeAn edge whose flow equals its capacity, that is, f(u, v) = c(u, v); no more flow can be sent through it.8 · Network Flow
search problemFinding whether a value occurs in a data set and, if so, where.4 · Searching Algorithms
selection sortA sort that selects the smallest item of the unsorted part in each pass and moves it to the front.3 · Sorting Algorithms
sentinelA special value placed at the end to remove the bounds check from a loop.4 · Searching Algorithms
(separate) chainingResolving collisions by keeping the keys that fall in the same cell in a list.4 · Searching Algorithms
shell sortAn insertion sort with a gradually shrinking gap (Donald Shell).3 · Sorting Algorithms
shortest pathA path between two vertices whose edge weights have the smallest sum.6 · Shortest Paths
shortest-path treeA tree rooted at the source in which the only path from the root to each vertex is a shortest path to that vertex.6 · Shortest Paths
single-source shortest pathsShortest paths from one source to all vertices (Dijkstra, Bellman-Ford).6 · Shortest Paths
sortingPutting items into ascending or descending order by a key.3 · Sorting Algorithms
source / sinkThe vertices where the flow starts (s) and ends (t).8 · Network Flow
space complexityHow the extra memory an algorithm uses beyond its input grows with the input size.2 · Algorithm Complexity
spanning treeAn acyclic subgraph of a connected graph that contains all of its vertices (V − 1 edges).7 · Minimum Spanning Trees
sparse / dense graphA graph is sparse if its number of edges is far below the maximum V(V − 1)/2 and dense if it is close to that value.5 · Graph Traversal
spurious hitIn Rabin-Karp, a window whose hash equals the pattern's hash although the characters differ; the verification is wasted.9 · String Matching and Compression
stable (sort)Describes a sort that preserves the relative order of items with equal keys.3 · Sorting Algorithms
stack frameThe space opened on the call stack for the parameters, local variables and return address when a method is called; it is removed when the method returns.2 · Algorithm Complexity
stringA finite sequence of characters from an alphabet.9 · String Matching and Compression
string matchingThe problem of finding all occurrences of a pattern in a text.9 · String Matching and Compression
strongly connected component (SCC)A maximal set of vertices in a directed graph in which there is a path from every vertex to every other vertex.5 · Graph Traversal
subset constructionA method that converts an NFA into a DFA that recognizes the same language; the DFA states are sets of NFA states.10 · Advanced String Algorithms
substringA part of a string made of consecutive characters.9 · String Matching and Compression
suffixA part taken from the end of a string.9 · String Matching and Compression
suffix arrayThe starting indices of all suffixes of a string, listed in lexicographic order of the suffixes.10 · Advanced String Algorithms
suffix trie / suffix treeA trie containing all suffixes of a string; its compressed form is the suffix tree.11 · Tries
swapExchanging the positions of two items.3 · Sorting Algorithms
ternary search trie (TST)A kind of trie whose nodes each hold one character together with less-than, equal and greater-than links.11 · Tries
tight boundA bound that is both a lower and an upper bound and so gives the growth exactly (Θ).2 · Algorithm Complexity
time complexityHow the number of basic operations grows with the input size.1 · Introduction
TimsortA hybrid sort that processes naturally sorted runs using insertion sort and merging.3 · Sorting Algorithms
topological sortAn ordering of the vertices of a directed acyclic graph in which every edge goes from left to right.5 · Graph Traversal
transitive closureA table that tells, for every pair i, j, whether there is a path from i to j; computed with the Boolean (and/or) version of Floyd-Warshall.6 · Shortest Paths
trap stateA non-accepting state of an automaton that cannot be left once entered, whatever the input.10 · Advanced String Algorithms
trie (prefix tree)A structure that stores strings in a tree whose character-labeled edges are shared by strings with a common prefix.11 · Tries
undirected graphA graph whose edges can be traversed in both directions.5 · Graph Traversal
union by rankA merging method that attaches the root of the shorter tree to the root of the taller tree.7 · Minimum Spanning Trees
union-find (disjoint sets)A structure that manages disjoint sets with find and union operations.7 · Minimum Spanning Trees
upper boundA limit that a value cannot exceed; O notation gives an upper bound.2 · Algorithm Complexity
vertex / nodeA point of a graph.5 · Graph Traversal
weighted graphA graph in which every edge is assigned a number (a weight or cost).5 · Graph Traversal
wildcard searchA search in which a wildcard character (.) in the pattern matches any letter.11 · Tries
worst caseThe input of a given size that requires the most operations.2 · Algorithm Complexity

Course page: Algorithms · © Sercan Külcü. All rights reserved.