Advanced 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
activity selectionSelecting the largest number of non-overlapping activities by always taking the one that finishes earliest.2 · Greedy Algorithms
adaptive adversaryAn adversary that observes the algorithm's random decisions and picks the next request accordingly; against it, most of the benefit of randomization is lost.8 · Online Algorithms
adversaryAn imaginary opponent that chooses the input that forces the algorithm into its worst case.8 · Online Algorithms
Amdahl's lawThe principle that the part of a computation that must stay sequential limits the maximum achievable speedup.9 · Parallel Algorithms
amplificationA technique that repeats a randomized algorithm independently to reduce its probability of error.7 · Randomized Algorithms
ant colony optimizationA method inspired by ants: artificial ants that build short tours deposit more pheromone on their edges, and pheromone evaporates over time.6 · Approximation Algorithms
approximation algorithmAn algorithm that produces, in polynomial time, a solution to an NP-hard problem that is provably within a guaranteed ratio of the optimum.6 · Approximation Algorithms
approximation ratioThe worst-case ratio between the algorithm's solution and the optimum (ρ).6 · Approximation Algorithms
approximation scheme (PTAS / FPTAS)A family of algorithms that, for every ε > 0, produces a solution within a factor of (1 + ε) of the optimum.6 · Approximation Algorithms
assignment problemThe problem of assigning n jobs to n people, one job per person, at the least total cost.5 · Branch and Bound
backtrackingA search that extends a partial solution step by step and, at a dead end, undoes the last choice and tries another option.4 · Backtracking
barrierA synchronization point that no processor can pass until all processors have reached it.9 · Parallel Algorithms
Belady's anomalyThe phenomenon that, under FIFO, increasing the number of frames can increase the number of page faults.8 · Online Algorithms
best-first searchA search strategy that expands the node whose bound is the most promising first.5 · Branch and Bound
bin packingThe problem of packing items of given sizes into the fewest bins of fixed capacity; it is NP-hard.2 · Greedy Algorithms
boundAn optimistic estimate of the best value obtainable from a branch.5 · Branch and Bound
branch and boundA method that branches over the state space, computes a bound for each branch, and prunes branches whose bound is worse than the best known solution.5 · Branch and Bound
branchingSplitting a subproblem into smaller subproblems.5 · Branch and Bound
cacheA small, fast memory that holds frequently used data.8 · Online Algorithms
canonical coin systemA coin system in which the greedy change-making algorithm uses the fewest coins for every amount.2 · Greedy Algorithms
Carmichael numberA composite number that passes the Fermat test for every base coprime to it.7 · Randomized Algorithms
chromatic numberThe smallest number of colors needed to color a graph so that no two nodes joined by an edge share a color.4 · Backtracking
closest pair of pointsFinding the two points that are closest to each other among a set of points in the plane.1 · Divide and Conquer
coin change problemForming a given amount using the fewest coins.2 · Greedy Algorithms
competitive analysisComparing an online algorithm against the best offline algorithm (OPT).8 · Online Algorithms
competitive ratioThe smallest c such that ALG ≤ c · OPT (+ a constant) holds for every input.8 · Online Algorithms
compulsory miss (cold miss)A page fault on the first distinct pages, which no policy can avoid because the cache starts empty.8 · Online Algorithms
concept driftA change in the distribution of the data over time; in incremental learning, old data becomes misleading under it.8 · Online Algorithms
constraint satisfaction problemThe problem of assigning values to variables so that all constraints are satisfied.4 · Backtracking
convergenceThe iterates getting steadily closer to the true value.6 · Approximation Algorithms
convex hullThe smallest convex polygon that contains a set of points.1 · Divide and Conquer
data streamContinuously arriving data that must be processed in a single pass using little memory.8 · Online Algorithms
dead nodeA node that has been expanded, found infeasible, or pruned because its bound is insufficient; it is never considered again.5 · Branch and Bound
decision problemA problem whose answer is yes or no.4 · Backtracking
depth-first branch and boundA branch and bound that explores live nodes with a stack (depth first), so its memory is limited by the depth.5 · Branch and Bound
distributed memoryAn arrangement in which each node has its own memory and data moves over the network as messages; it scales well but communication is expensive.9 · Parallel Algorithms
divide and conquerAn approach that splits a problem into smaller subproblems, solves them recursively, and combines the results.1 · Divide and Conquer
dynamic programming (DP)A design technique that solves overlapping subproblems once and reuses the stored results.3 · Dynamic Programming
E-node (expanding node)The node whose children, that is, subproblems, are currently being generated.5 · Branch and Bound
edge contractionMerging the two endpoints of an edge into a single node (Karger's algorithm).7 · Randomized Algorithms
efficiencySpeedup per processor: speedup / p.9 · Parallel Algorithms
entropyThe average amount of information per symbol of a source; a lower bound on the average length of a prefix-free code.2 · Greedy Algorithms
eviction policyThe rule that decides which page to remove when the cache is full (FIFO, LRU, OPT).8 · Online Algorithms
exchange argumentProving correctness by transforming an optimal solution so that it contains the greedy choice.2 · Greedy Algorithms
expected running timeThe expected value of a randomized algorithm's running time on a given input.7 · Randomized Algorithms
expected valueThe average of a random variable weighted by probabilities.7 · Randomized Algorithms
feasibleSatisfying all the constraints (said of a solution).5 · Branch and Bound
Fisher–Yates shuffleAn O(n) shuffle that produces every permutation with equal probability.7 · Randomized Algorithms
forward checkingImmediately removing conflicting values from the possible values of connected variables when a value is assigned to a variable.4 · Backtracking
fractional knapsackA problem in which items can be taken fractionally, solved greedily by value-to-weight ratio.2 · Greedy Algorithms
genetic algorithmA method that works with a population of solutions: good solutions are selected more often and combined by crossover, and mutation preserves diversity.6 · Approximation Algorithms
geometric distributionThe distribution of the number of trials up to the first success when each trial succeeds with probability p.7 · Randomized Algorithms
global optimumThe best of all solutions; local search stops at a local optimum and may fail to reach it.6 · Approximation Algorithms
graph coloringColoring nodes so that adjacent nodes receive different colors.4 · Backtracking
greedy algorithmAn algorithm that makes the choice that looks best at the moment at every step and never goes back.2 · Greedy Algorithms
greedy-choice propertyThe property that a locally best choice can lead to an optimal solution.2 · Greedy Algorithms
Hamiltonian cycleA cycle that passes through every node exactly once and returns to the start.6 · Approximation Algorithms
Hamiltonian pathA path that passes through every node exactly once.4 · Backtracking
hit (cache hit)Finding the requested page in the cache; it costs 0. If it is not found, a page fault occurs.8 · Online Algorithms
Huffman codingAn optimal prefix-free coding that gives short codes to frequent characters.2 · Greedy Algorithms
Hungarian methodAn algorithm that solves the assignment problem in O(n³) time.5 · Branch and Bound
incremental learningUpdating the model with each new piece of data without reprocessing the past.8 · Online Algorithms
incumbentThe value of the best complete solution found so far in branch and bound.5 · Branch and Bound
indicator random variableA random variable that takes the value 1 if an event occurs and 0 if it does not.7 · Randomized Algorithms
integer linear programming (ILP)Linear programming in which the variables must be integers.5 · Branch and Bound
job sequencing with deadlinesChoosing, from jobs that have deadlines, the schedule with the greatest total profit.2 · Greedy Algorithms
Karatsuba multiplicationA method that multiplies large numbers with three subproducts in O(n^1.585) time.1 · Divide and Conquer
0/1 knapsackA problem in which each item is either taken whole or not at all, maximizing value without exceeding the capacity.3 · Dynamic Programming
Las Vegas algorithmAn algorithm that always gives the correct answer but whose running time is random.7 · Randomized Algorithms
least recently used (LRU)A policy that, when the cache is full, removes the page that has gone unused for the longest time; its competitive ratio is k.8 · Online Algorithms
least-cost (LC) searchA search that expands the live node with the smallest estimated cost ĉ = f + ĝ.5 · Branch and Bound
linear congruential generator (LCG)The oldest and simplest pseudo-random number generator, producing the next number by (a · x + c) mod m; its low bits have a short period.7 · Randomized Algorithms
list schedulingGreedy scheduling that assigns each job to the machine that becomes free earliest.6 · Approximation Algorithms
list update problemThe problem of reducing access cost by reordering a list according to the items accessed.8 · Online Algorithms
live nodeA node generated but not yet expanded in branch and bound that is still promising; live nodes wait in a queue structure.5 · Branch and Bound
local optimumA solution none of whose neighboring solutions is better.6 · Approximation Algorithms
local searchA search that starts from a solution and improves it with small changes (for example 2-opt).6 · Approximation Algorithms
locality of referenceThe tendency of programs to access memory locations they used in the recent past rather than random ones; this is what makes LRU better than FIFO.8 · Online Algorithms
longest common subsequence (LCS)The longest sequence of characters that appears in the same relative order in two sequences, not necessarily contiguously.3 · Dynamic Programming
longest common substringThe longest piece that appears contiguously in both strings.3 · Dynamic Programming
longest increasing subsequence (LIS)The longest increasing sequence that can be selected from a sequence while preserving the order of its elements.3 · Dynamic Programming
longest processing time first (LPT)A scheduling rule that sorts jobs from largest to smallest and assigns each to the least loaded machine.6 · Approximation Algorithms
lost updateWhen two threads read and write the same value and one write overwrites the other.9 · Parallel Algorithms
LP relaxationObtaining a bound by dropping the integrality condition and solving the resulting linear program.5 · Branch and Bound
makespanThe moment the last job in a schedule finishes (C_max).6 · Approximation Algorithms
marking algorithmAn online caching policy that divides the sequence into phases and evicts only unmarked pages in each phase.8 · Online Algorithms
Markov's inequalityThe inequality P(X ≥ a) ≤ E[X] / a for a non-negative X.7 · Randomized Algorithms
matchingA set of edges no two of which share an endpoint.6 · Approximation Algorithms
matrix chain multiplicationThe problem of finding the parenthesization that multiplies a sequence of matrices with the fewest scalar multiplications.3 · Dynamic Programming
matroidA set structure that guarantees that the greedy algorithm finds the best solution.2 · Greedy Algorithms
maximum cliqueThe largest set of nodes in which every two nodes are adjacent.5 · Branch and Bound
maximum coverageThe problem of covering as many elements as possible by choosing at most k sets; the greedy choice achieves at least 1 − 1/e of the best.2 · Greedy Algorithms
medianThe middle value of sorted data.8 · Online Algorithms
memoizationStoring and reusing results computed in top-down recursion.3 · Dynamic Programming
message passingInformation that processors send to exchange data in distributed memory.9 · Parallel Algorithms
metaheuristicA general search strategy for escaping local optima (simulated annealing, genetic algorithm).6 · Approximation Algorithms
min-conflicts heuristicA local search that gives a conflicting variable the value that creates the fewest conflicts.4 · Backtracking
minimum cutA cut that splits a graph into two parts with the fewest edges (or the smallest capacity).7 · Randomized Algorithms
minimum remaining values (MRV)A heuristic for constraint problems that chooses first the variable with the fewest remaining possible values.4 · Backtracking
Monte Carlo algorithmAn algorithm with bounded running time whose answer may be wrong with a small probability.7 · Randomized Algorithms
move-to-front (MTF)A rule that moves the accessed item to the front of the list; it is 2-competitive.8 · Online Algorithms
moving averageUpdating the average of the last k values with each new value.8 · Online Algorithms
N-queens problemPlacing n queens on an n × n board so that none threatens another.4 · Backtracking
nearest neighbor heuristicA TSP heuristic that goes to the nearest unvisited city at each step.6 · Approximation Algorithms
NP-completeA problem that is both in NP and NP-hard.4 · Backtracking
NP-hardA problem to which every problem in NP can be reduced in polynomial time (at least as hard as NP).4 · Backtracking
oblivious adversaryAn adversary that knows the code of a randomized algorithm but cannot see its coin flips, and therefore fixes the request sequence in advance.8 · Online Algorithms
offline algorithmAn algorithm that knows the entire input in advance.8 · Online Algorithms
online algorithmAn algorithm that receives the input piece by piece and makes a decision at each step without knowing the future.8 · Online Algorithms
optimalThe best according to the objective function (said of a solution).6 · Approximation Algorithms
optimal substructureThe property that an optimal solution can be built from optimal solutions to its subproblems.3 · Dynamic Programming
optimization problemA problem whose answer is the best value rather than yes or no; it can often be converted into a decision problem.4 · Backtracking
overlapping subproblemsThe same subproblem appearing again and again in the recursion.3 · Dynamic Programming
page faultThe requested page not being in the cache.8 · Online Algorithms
pagingThe problem of deciding which pages to keep in a limited cache.8 · Online Algorithms
parallel algorithmAn algorithm that splits the work among several processors running at the same time.9 · Parallel Algorithms
partial solutionA solution built step by step in backtracking that is not yet complete.4 · Backtracking
pipeliningSplitting the work into stages and processing different data in the stages at the same time.9 · Parallel Algorithms
pivotThe element chosen to split the array into two parts in partitioning.7 · Randomized Algorithms
polynomial timeRunning time O(nᵏ) for some constant k.4 · Backtracking
power iterationA method that repeatedly multiplies a vector by a matrix so that it converges to the dominant eigenvalue and eigenvector.6 · Approximation Algorithms
PRAM modelAn abstract model made of processors that share a common memory and run in synchronous steps.9 · Parallel Algorithms
prefix sum (scan)At each position, the sum of the elements up to that position; computable in parallel with O(log n) depth.9 · Parallel Algorithms
prefix-free codeA code in which no codeword is a prefix of another codeword.2 · Greedy Algorithms
primality testTesting whether a number is prime (Miller–Rabin).7 · Randomized Algorithms
pruningRemoving from the search a branch that is known not to lead to a solution.4 · Backtracking
pseudo-polynomialRunning time that is polynomial in the numeric value in the input (for example W) rather than in the input length.3 · Dynamic Programming
pseudo-random numberA number that looks random but is produced by a deterministic generator.7 · Randomized Algorithms
quickselectFinding the k-th smallest element in expected O(n) time with a random pivot.7 · Randomized Algorithms
race conditionA situation where the result depends on the order in which threads run.9 · Parallel Algorithms
randomized algorithmAn algorithm that makes random choices in its steps.7 · Randomized Algorithms
reduced cost matrixA cost matrix from which row and column minima have been subtracted; the total subtracted is a lower bound for the TSP.5 · Branch and Bound
reductionTransforming instances of one problem into instances of another problem.6 · Approximation Algorithms
reservoir samplingMaintaining a uniform random sample of k items from a stream of unknown length.8 · Online Algorithms
running medianKeeping the median of the values in a stream up to date with two heaps.8 · Online Algorithms
satisfiability (SAT)The problem of asking whether some assignment of values makes a formula built from Boolean variables true; it is the first NP-complete problem.4 · Backtracking
schedulingThe problem of assigning jobs to machines or to time slots.6 · Approximation Algorithms
seedThe starting value of a pseudo-random number generator.7 · Randomized Algorithms
self-organizing listA list that adapts itself to usage by moving accessed items toward the front with a rule such as move-to-front or transpose.8 · Online Algorithms
shared memoryAn arrangement in which all processors see the same address space; communication is cheap but concurrent access must be controlled.9 · Parallel Algorithms
simulated annealingA metaheuristic that accepts worsening moves with a decreasing probability.6 · Approximation Algorithms
ski rental problemThe problem of choosing between renting and buying without knowing the future.8 · Online Algorithms
sliding windowA method that keeps a running total in a variable and, at each step, adds the new element and removes the oldest to update the value over the last k elements.8 · Online Algorithms
speedupSequential running time divided by parallel running time: T₁ / Tₚ.9 · Parallel Algorithms
stack algorithmA page replacement policy under which the set of pages in a larger memory always contains the set in a smaller one; it does not exhibit Belady's anomaly.8 · Online Algorithms
state-space treeA search tree in which partial solutions are nodes and choices are edges.4 · Backtracking
Strassen's algorithmA method that multiplies matrices with seven subproducts instead of eight, in O(n^2.81) time.1 · Divide and Conquer
strong liarFor a composite number, a base that is not a witness and so makes it look prime.7 · Randomized Algorithms
subproblemA smaller instance of the original problem.3 · Dynamic Programming
subset sumThe problem of deciding whether some subset has a sum equal to a given value.3 · Dynamic Programming
tabulationFilling in the subproblems in a table from smallest to largest (bottom-up).3 · Dynamic Programming
throughputThe number of jobs completed per unit of time; in a pipeline it grows by a factor equal to the number of stages.9 · Parallel Algorithms
top-down / bottom-upThe two forms of DP: recursion with memoization, or filling a table with a loop.3 · Dynamic Programming
traceback (solution reconstruction)Finding the solution itself by walking backward through the filled DP table.3 · Dynamic Programming
transpose (heuristic)A list reordering rule that swaps the accessed item with the one before it.8 · Online Algorithms
travelling salesman problem (TSP)Finding the shortest tour that visits every city once and returns to the start.6 · Approximation Algorithms
triangle inequalityThe condition d(a, c) ≤ d(a, b) + d(b, c) for every three points.6 · Approximation Algorithms
unbounded knapsackA knapsack problem in which each item can be taken any number of times.3 · Dynamic Programming
up-sweep / down-sweepThe two phases of Blelloch's prefix sum: the up-sweep builds partial sums from the leaves to the root, and the down-sweep carries to each node the sum of the nodes to its left, from the root to the leaves.9 · Parallel Algorithms
vertex coverA set of nodes that contains at least one endpoint of every edge.6 · Approximation Algorithms
witnessA base that proves a number is composite (Miller–Rabin).7 · Randomized Algorithms
work / spanThe total number of operations (T₁) and the longest chain of dependencies (T∞).9 · Parallel Algorithms
work stealingAn idle thread taking work from another thread's queue.9 · Parallel Algorithms
work-efficientA parallel algorithm whose work is of the same order as the running time of the best sequential algorithm for the same problem.9 · Parallel Algorithms

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