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.
| Term | Definition | Chapter |
|---|---|---|
| activity selection | Selecting the largest number of non-overlapping activities by always taking the one that finishes earliest. | 2 · Greedy Algorithms |
| adaptive adversary | An 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 |
| adversary | An imaginary opponent that chooses the input that forces the algorithm into its worst case. | 8 · Online Algorithms |
| Amdahl's law | The principle that the part of a computation that must stay sequential limits the maximum achievable speedup. | 9 · Parallel Algorithms |
| amplification | A technique that repeats a randomized algorithm independently to reduce its probability of error. | 7 · Randomized Algorithms |
| ant colony optimization | A 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 algorithm | An 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 ratio | The 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 problem | The problem of assigning n jobs to n people, one job per person, at the least total cost. | 5 · Branch and Bound |
| backtracking | A search that extends a partial solution step by step and, at a dead end, undoes the last choice and tries another option. | 4 · Backtracking |
| barrier | A synchronization point that no processor can pass until all processors have reached it. | 9 · Parallel Algorithms |
| Belady's anomaly | The phenomenon that, under FIFO, increasing the number of frames can increase the number of page faults. | 8 · Online Algorithms |
| best-first search | A search strategy that expands the node whose bound is the most promising first. | 5 · Branch and Bound |
| bin packing | The problem of packing items of given sizes into the fewest bins of fixed capacity; it is NP-hard. | 2 · Greedy Algorithms |
| bound | An optimistic estimate of the best value obtainable from a branch. | 5 · Branch and Bound |
| branch and bound | A 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 |
| branching | Splitting a subproblem into smaller subproblems. | 5 · Branch and Bound |
| cache | A small, fast memory that holds frequently used data. | 8 · Online Algorithms |
| canonical coin system | A coin system in which the greedy change-making algorithm uses the fewest coins for every amount. | 2 · Greedy Algorithms |
| Carmichael number | A composite number that passes the Fermat test for every base coprime to it. | 7 · Randomized Algorithms |
| chromatic number | The 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 points | Finding the two points that are closest to each other among a set of points in the plane. | 1 · Divide and Conquer |
| coin change problem | Forming a given amount using the fewest coins. | 2 · Greedy Algorithms |
| competitive analysis | Comparing an online algorithm against the best offline algorithm (OPT). | 8 · Online Algorithms |
| competitive ratio | The 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 drift | A change in the distribution of the data over time; in incremental learning, old data becomes misleading under it. | 8 · Online Algorithms |
| constraint satisfaction problem | The problem of assigning values to variables so that all constraints are satisfied. | 4 · Backtracking |
| convergence | The iterates getting steadily closer to the true value. | 6 · Approximation Algorithms |
| convex hull | The smallest convex polygon that contains a set of points. | 1 · Divide and Conquer |
| data stream | Continuously arriving data that must be processed in a single pass using little memory. | 8 · Online Algorithms |
| dead node | A node that has been expanded, found infeasible, or pruned because its bound is insufficient; it is never considered again. | 5 · Branch and Bound |
| decision problem | A problem whose answer is yes or no. | 4 · Backtracking |
| depth-first branch and bound | A 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 memory | An 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 conquer | An 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 contraction | Merging the two endpoints of an edge into a single node (Karger's algorithm). | 7 · Randomized Algorithms |
| efficiency | Speedup per processor: speedup / p. | 9 · Parallel Algorithms |
| entropy | The 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 policy | The rule that decides which page to remove when the cache is full (FIFO, LRU, OPT). | 8 · Online Algorithms |
| exchange argument | Proving correctness by transforming an optimal solution so that it contains the greedy choice. | 2 · Greedy Algorithms |
| expected running time | The expected value of a randomized algorithm's running time on a given input. | 7 · Randomized Algorithms |
| expected value | The average of a random variable weighted by probabilities. | 7 · Randomized Algorithms |
| feasible | Satisfying all the constraints (said of a solution). | 5 · Branch and Bound |
| Fisher–Yates shuffle | An O(n) shuffle that produces every permutation with equal probability. | 7 · Randomized Algorithms |
| forward checking | Immediately removing conflicting values from the possible values of connected variables when a value is assigned to a variable. | 4 · Backtracking |
| fractional knapsack | A problem in which items can be taken fractionally, solved greedily by value-to-weight ratio. | 2 · Greedy Algorithms |
| genetic algorithm | A 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 distribution | The distribution of the number of trials up to the first success when each trial succeeds with probability p. | 7 · Randomized Algorithms |
| global optimum | The best of all solutions; local search stops at a local optimum and may fail to reach it. | 6 · Approximation Algorithms |
| graph coloring | Coloring nodes so that adjacent nodes receive different colors. | 4 · Backtracking |
| greedy algorithm | An algorithm that makes the choice that looks best at the moment at every step and never goes back. | 2 · Greedy Algorithms |
| greedy-choice property | The property that a locally best choice can lead to an optimal solution. | 2 · Greedy Algorithms |
| Hamiltonian cycle | A cycle that passes through every node exactly once and returns to the start. | 6 · Approximation Algorithms |
| Hamiltonian path | A 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 coding | An optimal prefix-free coding that gives short codes to frequent characters. | 2 · Greedy Algorithms |
| Hungarian method | An algorithm that solves the assignment problem in O(n³) time. | 5 · Branch and Bound |
| incremental learning | Updating the model with each new piece of data without reprocessing the past. | 8 · Online Algorithms |
| incumbent | The value of the best complete solution found so far in branch and bound. | 5 · Branch and Bound |
| indicator random variable | A 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 deadlines | Choosing, from jobs that have deadlines, the schedule with the greatest total profit. | 2 · Greedy Algorithms |
| Karatsuba multiplication | A method that multiplies large numbers with three subproducts in O(n^1.585) time. | 1 · Divide and Conquer |
| 0/1 knapsack | A problem in which each item is either taken whole or not at all, maximizing value without exceeding the capacity. | 3 · Dynamic Programming |
| Las Vegas algorithm | An 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) search | A 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 scheduling | Greedy scheduling that assigns each job to the machine that becomes free earliest. | 6 · Approximation Algorithms |
| list update problem | The problem of reducing access cost by reordering a list according to the items accessed. | 8 · Online Algorithms |
| live node | A 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 optimum | A solution none of whose neighboring solutions is better. | 6 · Approximation Algorithms |
| local search | A search that starts from a solution and improves it with small changes (for example 2-opt). | 6 · Approximation Algorithms |
| locality of reference | The 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 substring | The 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 update | When two threads read and write the same value and one write overwrites the other. | 9 · Parallel Algorithms |
| LP relaxation | Obtaining a bound by dropping the integrality condition and solving the resulting linear program. | 5 · Branch and Bound |
| makespan | The moment the last job in a schedule finishes (C_max). | 6 · Approximation Algorithms |
| marking algorithm | An online caching policy that divides the sequence into phases and evicts only unmarked pages in each phase. | 8 · Online Algorithms |
| Markov's inequality | The inequality P(X ≥ a) ≤ E[X] / a for a non-negative X. | 7 · Randomized Algorithms |
| matching | A set of edges no two of which share an endpoint. | 6 · Approximation Algorithms |
| matrix chain multiplication | The problem of finding the parenthesization that multiplies a sequence of matrices with the fewest scalar multiplications. | 3 · Dynamic Programming |
| matroid | A set structure that guarantees that the greedy algorithm finds the best solution. | 2 · Greedy Algorithms |
| maximum clique | The largest set of nodes in which every two nodes are adjacent. | 5 · Branch and Bound |
| maximum coverage | The 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 |
| median | The middle value of sorted data. | 8 · Online Algorithms |
| memoization | Storing and reusing results computed in top-down recursion. | 3 · Dynamic Programming |
| message passing | Information that processors send to exchange data in distributed memory. | 9 · Parallel Algorithms |
| metaheuristic | A general search strategy for escaping local optima (simulated annealing, genetic algorithm). | 6 · Approximation Algorithms |
| min-conflicts heuristic | A local search that gives a conflicting variable the value that creates the fewest conflicts. | 4 · Backtracking |
| minimum cut | A 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 algorithm | An 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 average | Updating the average of the last k values with each new value. | 8 · Online Algorithms |
| N-queens problem | Placing n queens on an n × n board so that none threatens another. | 4 · Backtracking |
| nearest neighbor heuristic | A TSP heuristic that goes to the nearest unvisited city at each step. | 6 · Approximation Algorithms |
| NP-complete | A problem that is both in NP and NP-hard. | 4 · Backtracking |
| NP-hard | A problem to which every problem in NP can be reduced in polynomial time (at least as hard as NP). | 4 · Backtracking |
| oblivious adversary | An 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 algorithm | An algorithm that knows the entire input in advance. | 8 · Online Algorithms |
| online algorithm | An algorithm that receives the input piece by piece and makes a decision at each step without knowing the future. | 8 · Online Algorithms |
| optimal | The best according to the objective function (said of a solution). | 6 · Approximation Algorithms |
| optimal substructure | The property that an optimal solution can be built from optimal solutions to its subproblems. | 3 · Dynamic Programming |
| optimization problem | A problem whose answer is the best value rather than yes or no; it can often be converted into a decision problem. | 4 · Backtracking |
| overlapping subproblems | The same subproblem appearing again and again in the recursion. | 3 · Dynamic Programming |
| page fault | The requested page not being in the cache. | 8 · Online Algorithms |
| paging | The problem of deciding which pages to keep in a limited cache. | 8 · Online Algorithms |
| parallel algorithm | An algorithm that splits the work among several processors running at the same time. | 9 · Parallel Algorithms |
| partial solution | A solution built step by step in backtracking that is not yet complete. | 4 · Backtracking |
| pipelining | Splitting the work into stages and processing different data in the stages at the same time. | 9 · Parallel Algorithms |
| pivot | The element chosen to split the array into two parts in partitioning. | 7 · Randomized Algorithms |
| polynomial time | Running time O(nᵏ) for some constant k. | 4 · Backtracking |
| power iteration | A method that repeatedly multiplies a vector by a matrix so that it converges to the dominant eigenvalue and eigenvector. | 6 · Approximation Algorithms |
| PRAM model | An 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 code | A code in which no codeword is a prefix of another codeword. | 2 · Greedy Algorithms |
| primality test | Testing whether a number is prime (Miller–Rabin). | 7 · Randomized Algorithms |
| pruning | Removing from the search a branch that is known not to lead to a solution. | 4 · Backtracking |
| pseudo-polynomial | Running 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 number | A number that looks random but is produced by a deterministic generator. | 7 · Randomized Algorithms |
| quickselect | Finding the k-th smallest element in expected O(n) time with a random pivot. | 7 · Randomized Algorithms |
| race condition | A situation where the result depends on the order in which threads run. | 9 · Parallel Algorithms |
| randomized algorithm | An algorithm that makes random choices in its steps. | 7 · Randomized Algorithms |
| reduced cost matrix | A 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 |
| reduction | Transforming instances of one problem into instances of another problem. | 6 · Approximation Algorithms |
| reservoir sampling | Maintaining a uniform random sample of k items from a stream of unknown length. | 8 · Online Algorithms |
| running median | Keeping 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 |
| scheduling | The problem of assigning jobs to machines or to time slots. | 6 · Approximation Algorithms |
| seed | The starting value of a pseudo-random number generator. | 7 · Randomized Algorithms |
| self-organizing list | A 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 memory | An arrangement in which all processors see the same address space; communication is cheap but concurrent access must be controlled. | 9 · Parallel Algorithms |
| simulated annealing | A metaheuristic that accepts worsening moves with a decreasing probability. | 6 · Approximation Algorithms |
| ski rental problem | The problem of choosing between renting and buying without knowing the future. | 8 · Online Algorithms |
| sliding window | A 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 |
| speedup | Sequential running time divided by parallel running time: T₁ / Tₚ. | 9 · Parallel Algorithms |
| stack algorithm | A 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 tree | A search tree in which partial solutions are nodes and choices are edges. | 4 · Backtracking |
| Strassen's algorithm | A method that multiplies matrices with seven subproducts instead of eight, in O(n^2.81) time. | 1 · Divide and Conquer |
| strong liar | For a composite number, a base that is not a witness and so makes it look prime. | 7 · Randomized Algorithms |
| subproblem | A smaller instance of the original problem. | 3 · Dynamic Programming |
| subset sum | The problem of deciding whether some subset has a sum equal to a given value. | 3 · Dynamic Programming |
| tabulation | Filling in the subproblems in a table from smallest to largest (bottom-up). | 3 · Dynamic Programming |
| throughput | The 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-up | The 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 inequality | The condition d(a, c) ≤ d(a, b) + d(b, c) for every three points. | 6 · Approximation Algorithms |
| unbounded knapsack | A knapsack problem in which each item can be taken any number of times. | 3 · Dynamic Programming |
| up-sweep / down-sweep | The 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 cover | A set of nodes that contains at least one endpoint of every edge. | 6 · Approximation Algorithms |
| witness | A base that proves a number is composite (Miller–Rabin). | 7 · Randomized Algorithms |
| work / span | The total number of operations (T₁) and the longest chain of dependencies (T∞). | 9 · Parallel Algorithms |
| work stealing | An idle thread taking work from another thread's queue. | 9 · Parallel Algorithms |
| work-efficient | A 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 |
No terms match your search.
Course page: Advanced Algorithms · © Sercan Külcü. All rights reserved.