HOME

TheInfoList



OR:

The following is a list of well-known
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s along with one-line descriptions for each.


Automated planning


Combinatorial algorithms


General combinatorial algorithms

* Brent's algorithm: finds a cycle in function value iterations using only two iterators * Floyd's cycle-finding algorithm: finds a cycle in function value iterations *
Gale–Shapley algorithm In mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm or propose-and-reject algorithm) is an algorithm for finding a solution to the stable matching problem, named for David ...
: solves the stable marriage problem *
Pseudorandom number generator A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
s (uniformly distributed—see also List of pseudorandom number generators for other PRNGs with varying degrees of convergence and varying statistical quality): ** ACORN generator ** Blum Blum Shub ** Lagged Fibonacci generator **
Linear congruential generator A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generat ...
**
Mersenne Twister The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by and . Its name derives from the fact that its period length is chosen to be a Mersenne prime. The Mersenne Twister was designed specifically to re ...


Graph algorithms

* Coloring algorithm: Graph coloring algorithm. *
Hopcroft–Karp algorithm In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of ...
: convert a bipartite graph to a
maximum cardinality matching Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is ...
*
Hungarian algorithm The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hu ...
: algorithm for finding a
perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
* Prüfer coding: conversion between a labeled tree and its
Prüfer sequence In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on ''n'' vertices has length ''n'' − 2, and can be ...
* Tarjan's off-line lowest common ancestors algorithm: computes
lowest common ancestor In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes and in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and as descendants, where ...
s for pairs of nodes in a tree * Topological sort: finds linear order of nodes (e.g. jobs) based on their dependencies.


Graph drawing

* Force-based algorithms (also known as force-directed algorithms or spring-based algorithm) * Spectral layout


Network theory

* Network analysis ** Link analysis *** Girvan–Newman algorithm: detect communities in complex systems *** Web link analysis **** Hyperlink-Induced Topic Search (HITS) (also known as Hubs and authorities) ****
PageRank PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. Accordi ...
**** TrustRank *
Flow network In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations re ...
s **
Dinic's algorithm Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in O(V^2 E) ...
: is a strongly polynomial algorithm for computing the maximum flow in a
flow network In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations re ...
. **
Edmonds–Karp algorithm In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(, V, , E, ^2) time. The algorithm was first published by Yefim Dinitz (whose name is als ...
: implementation of Ford–Fulkerson ** Ford–Fulkerson algorithm: computes the maximum flow in a graph ** Karger's algorithm: a Monte Carlo method to compute the minimum cut of a connected graph ** Push–relabel algorithm: computes a maximum flow in a graph


Routing for graphs

* Edmonds' algorithm (also known as Chu–Liu/Edmonds' algorithm): find maximum or minimum branchings * Euclidean minimum spanning tree: algorithms for computing the minimum spanning tree of a set of points in the plane *
Longest path problem In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path (graph theory), path of maximum length in a given Graph (discrete mathematics), graph. A path is called ''simple'' if it does not ha ...
: find a simple path of maximum length in a given graph *
Minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...
** Borůvka's algorithm **
Kruskal's algorithm Kruskal's algorithm finds a minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. (A minimum spanning tree of a connected graph is a subset of the edges that forms a tree that ...
**
Prim's algorithm In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every ...
**
Reverse-delete algorithm The reverse-delete algorithm is an algorithm in graph theory used to obtain a minimum spanning tree from a given connected, edge-weighted graph. It first appeared in , but it should not be confused with Kruskal's algorithm which appears in the sam ...
* Nonblocking minimal spanning switch say, for a
telephone exchange telephone exchange, telephone switch, or central office is a telecommunications system used in the public switched telephone network (PSTN) or in large enterprises. It interconnects telephone subscriber lines or virtual circuits of digital syste ...
*
Shortest path problem In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between t ...
**
Bellman–Ford algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it i ...
: computes shortest paths in a weighted graph (where some of the edge weights may be negative) **
Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...
: computes shortest paths in a graph with non-negative edge weights **
Floyd–Warshall algorithm In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with p ...
: solves the all pairs shortest path problem in a weighted, directed graph ** Johnson's algorithm: all pairs shortest path algorithm in sparse weighted directed graph *
Transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinit ...
problem: find the
transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinit ...
of a given binary relation *
Traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
**
Christofides algorithm The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle ine ...
** Nearest neighbour algorithm * Warnsdorff's rule: a heuristic method for solving the
Knight's tour A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again im ...
problem


Graph search

* A*: special case of best-first search that uses heuristics to improve speed * B*: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals) *
Backtracking Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...
: abandons partial solutions when they are found not to satisfy a complete solution *
Beam search In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an optimization of best-first search that reduces its memory requirements. Best-first sea ...
: is a heuristic search algorithm that is an optimization of
best-first search Best-first search is a class of search algorithms, which explore a graph by expanding the most promising node chosen according to a specified rule. Judea Pearl described the best-first search as estimating the promise of node ''n'' by a "heuristic ...
that reduces its memory requirement * Beam stack search: integrates backtracking with
beam search In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an optimization of best-first search that reduces its memory requirements. Best-first sea ...
*
Best-first search Best-first search is a class of search algorithms, which explore a graph by expanding the most promising node chosen according to a specified rule. Judea Pearl described the best-first search as estimating the promise of node ''n'' by a "heuristic ...
: traverses a graph in the order of likely importance using a
priority queue In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...
* Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph *
Breadth-first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next d ...
: traverses a graph level by level * Brute-force search: an exhaustive and reliable search method, but computationally inefficient in many applications * D*: an incremental heuristic search algorithm *
Depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alo ...
: traverses a graph branch by branch *
Dijkstra's algorithm Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...
: a special case of A* for which no heuristic function is used * General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine. * Iterative deepening depth-first search (IDDFS): a state space search strategy * Jump point search: an optimization to A* which may reduce computation time by an order of magnitude using further heuristics * Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph *
Uniform-cost search Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...
: a
tree search In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. S ...
that finds the lowest-cost route where costs vary *
SSS* SSS* is a search algorithm, introduced by George Stockman in 1979, that conducts a state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm. SSS* is based on the notion of solution trees. Info ...
: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm * F*: special algorithm to merge the two arrays


Subgraphs

* Cliques ** Bron–Kerbosch algorithm: a technique for finding maximal cliques in an undirected graph **
MaxCliqueDyn maximum clique algorithm The MaxCliqueDyn algorithm is an algorithm for finding a maximum clique in an undirected graph. It is based on a basic algorithm (MaxClique algorithm) which finds a maximum clique of bounded size. The bound is found using improved coloring algor ...
: find a maximum clique in an undirected graph * Strongly connected components **
Path-based strong component algorithm In graph theory, the strongly connected components of a directed graph may be found using an algorithm that uses depth-first search in combination with two stacks, one to keep track of the vertices in the current component and the second to keep ...
** Kosaraju's algorithm **
Tarjan's strongly connected components algorithm Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's ...
* Subgraph isomorphism problem


Sequence algorithms


Approximate sequence matching

*
Bitap algorithm The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates–Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given patter ...
: fuzzy algorithm that determines if strings are approximately equal. * Phonetic algorithms ** Daitch–Mokotoff Soundex: a Soundex refinement which allows matching of Slavic and Germanic surnames ** Double Metaphone: an improvement on Metaphone ** Match rating approach: a phonetic algorithm developed by Western Airlines ** Metaphone: an algorithm for indexing words by their sound, when pronounced in English **
NYSIIS The New York State Identification and Intelligence System Phonetic Code, commonly known as NYSIIS, is a phonetic algorithm devised in 1970 as part of the New York State Identification and Intelligence System (now a part of the New York State Divisio ...
: phonetic algorithm, improves on Soundex ** Soundex: a phonetic algorithm for indexing names by sound, as pronounced in English *
String metric In mathematics and computer science, a string metric (also known as a string similarity metric or string distance function) is a metric that measures distance ("inverse similarity") between two text strings for approximate string matching or co ...
s: computes a similarity or dissimilarity (distance) score between two pairs of text strings **
Damerau–Levenshtein distance In information theory and computer science, the Damerau–Levenshtein distance (named after Frederick J. Damerau and Vladimir I. Levenshtein.) is a string metric for measuring the edit distance between two sequences. Informally, the Damerau–Leve ...
: computes a distance measure between two strings, improves on Levenshtein distance ** Dice's coefficient (also known as the Dice coefficient): a similarity measure related to the
Jaccard index The Jaccard index, also known as the Jaccard similarity coefficient, is a statistic used for gauging the similarity and diversity of sample sets. It was developed by Grove Karl Gilbert in 1884 as his ratio of verification (v) and now is fre ...
**
Hamming distance In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chang ...
: sum number of positions which are different ** Jaro–Winkler distance: is a measure of similarity between two strings ** Levenshtein edit distance: computes a metric for the amount of difference between two sequences *
Trigram search Trigram search is a method of searching for text when the exact syntax or spelling of the target object is not precisely known or when queries may be regular expressions. It finds objects which match the maximum number of three consecutive charac ...
: search for text when the exact syntax or spelling of the target object is not precisely known


Selection algorithms

* Quickselect * Introselect


Sequence search

*
Linear search In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. A linear search runs in at ...
: locates an item in an unsorted sequence * Selection algorithm: finds the ''k''th largest item in a sequence * Ternary search: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa * Sorted lists **
Binary search algorithm In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
: locates an item in a sorted sequence ** Fibonacci search technique: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of
Fibonacci numbers In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
** Jump search (or block search): linear search on a smaller subset of the sequence ** Predictive search: binary-like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search. **
Uniform binary search Uniform binary search is an optimization of the classic binary search algorithm invented by Donald Knuth and given in Knuth's ''The Art of Computer Programming''. It uses a lookup table to update a single array index, rather than taking the midpoint ...
: an optimization of the classic binary search algorithm


Sequence merging

* Simple merge algorithm * k-way merge algorithm * Union (merge, with elements on the output not repeated)


Sequence permutations

* Fisher–Yates shuffle (also known as the Knuth shuffle): randomly shuffle a finite set * Schensted algorithm: constructs a pair of Young tableaux from a permutation *
Steinhaus–Johnson–Trotter algorithm The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of n elements. Ea ...
(also known as the Johnson–Trotter algorithm): generates permutations by transposing elements * Heap's permutation generation algorithm: interchange elements to generate next permutation


Sequence combinations


Sequence alignment

* Dynamic time warping: measure similarity between two sequences which may vary in time or speed * Hirschberg's algorithm: finds the least cost
sequence alignment In bioinformatics, a sequence alignment is a way of arranging the sequences of DNA, RNA, or protein to identify regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between the sequences. Ali ...
between two sequences, as measured by their Levenshtein distance * Needleman–Wunsch algorithm: find global alignment between two sequences * Smith–Waterman algorithm: find local sequence alignment


Sequence sorting

* Exchange sorts **
Bubble sort Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes ...
: for each pair of indices, swap the items if out of order **
Cocktail shaker sort Cocktail shaker sort, also known as bidirectional bubble sort, cocktail sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuffle sort, or shuttle sort, is an extension of bubble sort. The algorithm extends bub ...
or bidirectional bubble sort, a bubble sort traversing the list alternately from front to back and back to front **
Comb sort Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz and Artur Borowy in 1980, later rediscovered (and given the name "Combsort") by Stephen Lacey and Richard Box in 1991. Comb sort improves on bubble ...
**
Gnome sort Gnome sort (nicknamed stupid sort) is a variation of the insertion sort sorting algorithm that does not use nested loops. Gnome sort was originally proposed by Iranian computer scientist Hamid Sarbazi-Azad (professor of Computer Science and Eng ...
** Odd–even sort **
Quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice * Humorous or ineffective **
Bogosort In computer science, bogosort (also known as permutation sort, stupid sort, slowsort or bozosort) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one t ...
** Stooge sort * Hybrid ** Flashsort ** Introsort: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level **
Timsort Timsort is a hybrid, stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algor ...
: adaptative algorithm derived from merge sort and insertion sort. Used in Python 2.3 and up, and Java SE 7. * Insertion sorts **
Insertion sort Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Howe ...
: determine where the current item belongs in the list of sorted ones, and insert it there ** Library sort ** Patience sorting ** Shell sort: an attempt to improve insertion sort ** Tree sort (binary tree sort): build binary tree, then traverse it to create sorted list ** Cycle sort: in-place with theoretically optimal number of writes * Merge sorts **
Merge sort In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...
: sort the first and second half of the list separately, then merge the sorted lists ** Slowsort **
Strand sort Strand sort is a recursive sorting algorithm that sorts items of a list into increasing order. It has O(n2) worst time complexity which occurs when the input list is reverse sorted. It has a best case time complexity In computer science, the ...
* Non-comparison sorts **
Bead sort Bead sort, also called gravity sort, is a natural computing, natural sorting algorithm, developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002, and published in ''The Bulletin of the European Association for Theoret ...
** Bucket sort ** Burstsort: build a compact, cache efficient
burst trie Burst may refer to: *Burst mode (disambiguation), a mode of operation where events occur in rapid succession **Burst transmission, a term in telecommunications **Burst switching, a feature of some packet-switched networks **Bursting, a signaling mo ...
and then traverse it to create sorted output **
Counting sort In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small positive integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that possess d ...
** Pigeonhole sort **
Postman sort Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying th ...
: variant of Bucket sort which takes advantage of hierarchical structure **
Radix sort In computer science, radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process ...
: sorts strings letter by letter * Selection sorts **
Heapsort In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...
: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list **
Selection sort In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(''n''2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is n ...
: pick the smallest of the remaining elements, add it to the end of the sorted list ** Smoothsort * Other ** Bitonic sorter **
Pancake sorting Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A ''pancake number'' is the minimum number o ...
** Spaghetti sort ** Topological sort * Unknown class ** Samplesort


Subsequences

*
Longest common subsequence problem The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, su ...
: Find the longest subsequence common to all sequences in a set of sequences *
Longest increasing subsequence problem In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subs ...
: Find the longest increasing subsequence of a given sequence *
Ruzzo–Tompa algorithm The Ruzzo–Tompa algorithm or the RT algorithm is a linear-time algorithm for finding all non-overlapping, contiguous, maximal scoring subsequences in a sequence of real numbers. The Ruzzo–Tompa algorithm was proposed by Walter L. Ruzzo and Mart ...
: Find all non-overlapping, contiguous, maximal scoring subsequences in a sequence of real numbers * Shortest common supersequence problem: Find the shortest supersequence that contains two or more sequences as subsequences


Substrings

*
Kadane's algorithm In computer science, the maximum sum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A ...nof numbers. Formally, the task is ...
: finds the contiguous subarray with largest sum in an array of numbers * Longest common substring problem: find the longest string (or strings) that is a substring (or are substrings) of two or more strings * Substring search ** Aho–Corasick string matching algorithm:
trie In computer science, a trie, also called digital tree or prefix tree, is a type of ''k''-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes d ...
based algorithm for finding all substring matches to any of a finite set of strings **
Boyer–Moore string-search algorithm In computer science, the Boyer–Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. ...
: amortized linear ( sublinear in most times) algorithm for substring search ** Boyer–Moore–Horspool algorithm: Simplification of Boyer–Moore **
Knuth–Morris–Pratt algorithm In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies ...
: substring search which bypasses reexamination of matched characters ** Rabin–Karp string search algorithm: searches multiple patterns efficiently ** Zhu–Takaoka string matching algorithm: a variant of Boyer–Moore * Ukkonen's algorithm: a linear-time, online algorithm for constructing
suffix tree In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow parti ...
s * Matching wildcards ** Rich Salz' wildmat: a widely used
open-source Open source is source code that is made freely available for possible modification and redistribution. Products include permission to use the source code, design documents, or content of the product. The open-source model is a decentralized sof ...
recursive algorithm ** Krauss matching wildcards algorithm: an open-source non-recursive algorithm


Computational mathematics


Abstract algebra

*
Chien search In abstract algebra, the Chien search, named after Robert Tienwen Chien, is a fast algorithm for determining roots of polynomials defined over a finite field. Chien search is commonly used to find the roots of error-locator polynomials encountered i ...
: a recursive algorithm for determining roots of polynomials defined over a finite field *
Schreier–Sims algorithm The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, test membership (is a given permutation ...
: computing a base and strong generating set (BSGS) of a permutation group *
Todd–Coxeter algorithm In group theory, the Todd–Coxeter algorithm, created by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group ''G'' by generators and relations and a subgroup ''H'' of ...
: Procedure for generating
coset In mathematics, specifically group theory, a subgroup of a group may be used to decompose the underlying set of into disjoint, equal-size subsets called cosets. There are ''left cosets'' and ''right cosets''. Cosets (both left and right) ...
s.


Computer algebra

* Buchberger's algorithm: finds a
Gröbner basis In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring over a field . A Grö ...
*
Cantor–Zassenhaus algorithm In computational algebra, the Cantor–Zassenhaus algorithm is a method for factoring polynomials over finite fields (also called Galois fields). The algorithm consists mainly of exponentiation and polynomial GCD computations. It was invented by ...
: factor polynomials over finite fields * Faugère F4 algorithm: finds a Gröbner basis (also mentions the F5 algorithm) * Gosper's algorithm: find sums of hypergeometric terms that are themselves hypergeometric terms *
Knuth–Bendix completion algorithm The Knuth–Bendix completion algorithm (named after Donald Knuth and Peter Bendix) is a semi-decision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system. When the algorithm succeeds, it effective ...
: for
rewriting In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduc ...
rule systems * Multivariate division algorithm: for
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An ex ...
s in several indeterminates *
Pollard's kangaroo algorithm In computational number theory and computational algebra, Pollard's kangaroo algorithm (also Pollard's lambda algorithm, see Naming below) is an algorithm for solving the discrete logarithm problem. The algorithm was introduced in 1978 by the nu ...
(also known as Pollard's lambda algorithm ): an algorithm for solving the discrete logarithm problem *
Polynomial long division In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, becau ...
: an algorithm for dividing a polynomial by another polynomial of the same or lower degree *
Risch algorithm In symbolic computation, the Risch algorithm is a method of indefinite integration used in some computer algebra systems to find antiderivatives. It is named after the American mathematician Robert Henry Risch, a specialist in computer algebra w ...
: an algorithm for the calculus operation of indefinite integration (i.e. finding antiderivatives)


Geometry

*
Closest pair problem The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean ...
: find the pair of points (from a set of points) with the smallest distance between them *
Collision detection Collision detection is the computational problem of detecting the intersection (Euclidean geometry), intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing ...
algorithms: check for the collision or intersection of two given solids * Cone algorithm: identify surface points * Convex hull algorithms: determining the convex hull of a set of points **
Graham scan Graham's scan is a method of finding the convex hull of a finite set of points in the plane with time complexity O(''n'' log ''n''). It is named after Ronald Graham, who published the original algorithm in 1972. The algorithm finds all vertices ...
** Quickhull ** Gift wrapping algorithm or Jarvis march ** Chan's algorithm ** Kirkpatrick–Seidel algorithm * Euclidean distance transform: computes the distance between every point in a grid and a discrete collection of points. *
Geometric hashing In computer science, geometric hashing is a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an affine transformation, though extensions exist to other object representations and transformat ...
: a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an
affine transformation In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles. More generall ...
* Gilbert–Johnson–Keerthi distance algorithm: determining the smallest distance between two
convex Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytop ...
shapes. *
Jump-and-Walk algorithm Jump-and-Walk is an algorithm for point location in triangulation In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points. Applications In survey ...
: an algorithm for point location in triangulations *
Laplacian smoothing Laplacian smoothing is an algorithm to smooth a polygonal mesh. For each vertex in a mesh, a new position is chosen based on local information (such as the position of neighbours) and the vertex is moved there. In the case that a mesh is topolo ...
: an algorithm to smooth a polygonal mesh * Line segment intersection: finding whether lines intersect, usually with a sweep line algorithm ** Bentley–Ottmann algorithm ** Shamos–Hoey algorithm * Minimum bounding box algorithms: find the oriented minimum bounding box enclosing a set of points *
Nearest neighbor search Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function ...
: find the nearest point or points to a query point * Point in polygon algorithms: tests whether a given point lies within a given polygon * Point set registration algorithms: finds the transformation between two point sets to optimally align them. * Rotating calipers: determine all antipodal pairs of points and vertices on a
convex polygon In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a ...
or convex hull. *
Shoelace algorithm The shoelace formula, shoelace algorithm, or shoelace method (also known as Gauss's area formula and the surveyor's formula) is a mathematical algorithm to determine the area of a simple polygon whose vertices are described by their Cartesian co ...
: determine the area of a polygon whose vertices are described by ordered pairs in the plane *
Triangulation In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points. Applications In surveying Specifically in surveying, triangulation involves only angle ...
**
Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle ...
*** Ruppert's algorithm (also known as Delaunay refinement): create quality Delaunay triangulations *** Chew's second algorithm: create quality constrained Delaunay triangulations **
Marching triangles In computer graphics, the problem of transforming a cloud of points on the surface of a three-dimensional object into a polygon mesh for the object can be solved by a technique called marching triangles. This provides a faster alternative to other m ...
: reconstruct two-dimensional surface geometry from an unstructured
point cloud Point or points may refer to: Places * Point, Lewis, a peninsula in the Outer Hebrides, Scotland * Point, Texas, a city in Rains County, Texas, United States * Point, the NE tip and a ferry terminal of Lismore, Inner Hebrides, Scotland * Point ...
**
Polygon triangulation In computational geometry, polygon triangulation is the partition of a polygonal area ( simple polygon) into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is . Triangulations may ...
algorithms: decompose a polygon into a set of triangles **
Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed ...
s, geometric
dual Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual (grammatical ...
of
Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle ...
*** Bowyer–Watson algorithm: create voronoi diagram in any number of dimensions *** Fortune's Algorithm: create voronoi diagram **
Quasitriangulation A quasi-triangulation is a subdivision of a geometric object into simplices, where vertices are not points but arbitrary sloped line segments. This division is not a triangulation in the geometric sense. It is a topological triangulation, however ...


Number theoretic algorithms

*
Binary GCD algorithm The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conv ...
: Efficient way of calculating GCD. * Booth's multiplication algorithm *
Chakravala method The ''chakravala'' method ( sa, चक्रवाल विधि) is a cyclic algorithm to solve indeterminate quadratic equations, including Pell's equation. It is commonly attributed to Bhāskara II, (c. 1114 – 1185 CE)Hoiberg & Ramchandani ...
: a cyclic algorithm to solve indeterminate quadratic equations, including
Pell's equation Pell's equation, also called the Pell–Fermat equation, is any Diophantine equation of the form x^2 - ny^2 = 1, where ''n'' is a given positive nonsquare integer, and integer solutions are sought for ''x'' and ''y''. In Cartesian coordinate ...
*
Discrete logarithm In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log' ...
: ** Baby-step giant-step ** Index calculus algorithm ** Pollard's rho algorithm for logarithms ** Pohlig–Hellman algorithm *
Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an ...
: computes the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' i ...
*
Extended Euclidean algorithm In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ...
: also solves the equation ''ax'' + ''by'' = ''c'' * Integer factorization: breaking an integer into its
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
factors **
Congruence of squares In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms. Derivation Given a positive integer ''n'', Fermat's factorization method relies on finding numbers ''x'' and ''y'' satisfying the equal ...
** Dixon's algorithm ** Fermat's factorization method **
General number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\le ...
** Lenstra elliptic curve factorization ** Pollard's ''p'' − 1 algorithm ** Pollard's rho algorithm ** prime factorization algorithm ** Quadratic sieve **
Shor's algorithm Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm runs in polynomial ...
** Special number field sieve ** Trial division * Multiplication algorithms: fast multiplication of two numbers ** Karatsuba algorithm ** Schönhage–Strassen algorithm ** Toom–Cook multiplication *
Modular square root In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic non ...
: computing square roots modulo a prime number ** Tonelli–Shanks algorithm **
Cipolla's algorithm In computational number theory, Cipolla's algorithm is a technique for solving a congruence of the form :x^2\equiv n \pmod, where x,n \in \mathbf_, so ''n'' is the square of ''x'', and where p is an odd prime. Here \mathbf_p denotes the finite fi ...
** Berlekamp's root finding algorithm * Odlyzko–Schönhage algorithm: calculates nontrivial zeroes of the Riemann zeta function * Lenstra–Lenstra–Lovász algorithm (also known as LLL algorithm): find a short, nearly orthogonal lattice basis in polynomial time *
Primality test A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating wh ...
s: determining whether a given number is
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
** AKS primality test **
Baillie–PSW primality test The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff. The Bailli ...
** Fermat primality test ** Lucas primality test ** Miller–Rabin primality test ** Sieve of Atkin **
Sieve of Eratosthenes In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime ...
** Sieve of Sundaram


Numerical algorithms


Differential equation solving

* Euler method * Backward Euler method * Trapezoidal rule (differential equations) *
Linear multistep method Linear multistep methods are used for the numerical solution of ordinary differential equations. Conceptually, a numerical method starts from an initial point and then takes a short step forward in time to find the next solution point. The proce ...
s *
Runge–Kutta methods In numerical analysis, the Runge–Kutta methods ( ) are a family of implicit and explicit iterative methods, which include the Euler method, used in temporal discretization for the approximate solutions of simultaneous nonlinear equations. Th ...
**
Euler integration In mathematics and computational science, the Euler method (also called forward Euler method) is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic explicit met ...
*
Multigrid method In numerical analysis, a multigrid method (MG method) is an algorithm for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in problems exhi ...
s (MG methods), a group of algorithms for solving differential equations using a hierarchy of discretizations *
Partial differential equation In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a multivariable function. The function is often thought of as an "unknown" to be solved for, similarly to ...
: ** Finite difference method **
Crank–Nicolson method In numerical analysis, the Crank–Nicolson method is a finite difference method used for numerically solving the heat equation and similar partial differential equations. It is a second-order method in time. It is implicit in time, can be wri ...
for diffusion equations ** Lax–Wendroff for wave equations * Verlet integration (): integrate Newton's equations of motion


Elementary and special functions

* Computation of π: ** Borwein's algorithm: an algorithm to calculate the value of 1/π **
Gauss–Legendre algorithm The Gauss–Legendre algorithm is an algorithm to compute the digits of . It is notable for being rapidly convergent, with only 25 iterations producing 45 million correct digits of . However, it has some drawbacks (for example, it is computer ...
: computes the digits of pi ** Chudnovsky algorithm: a fast method for calculating the digits of π ** Bailey–Borwein–Plouffe formula: (BBP formula) a spigot algorithm for the computation of the nth binary digit of π *
Division algorithm A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software. Di ...
s: for computing quotient and/or remainder of two numbers ** Long division **
Restoring division A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software. D ...
** Non-restoring division **
SRT division A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software. Divis ...
** Newton–Raphson division: uses
Newton's method In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real ...
to find the reciprocal of D, and multiply that reciprocal by N to find the final quotient Q. **
Goldschmidt division A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software. Di ...
* Hyperbolic and Trigonometric Functions: ** BKM algorithm: computes elementary functions using a table of logarithms ** CORDIC: computes hyperbolic and trigonometric functions using a table of arctangents * Exponentiation: ** Addition-chain exponentiation: exponentiation by positive integer powers that requires a minimal number of multiplications ** Exponentiating by squaring: an algorithm used for the fast computation of large integer powers of a number * Montgomery reduction: an algorithm that allows
modular arithmetic In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his bo ...
to be performed efficiently when the modulus is large * Multiplication algorithms: fast multiplication of two numbers ** Booth's multiplication algorithm: a multiplication algorithm that multiplies two signed binary numbers in two's complement notation ** Fürer's algorithm: an integer multiplication algorithm for very large numbers possessing a very low asymptotic complexity ** Karatsuba algorithm: an efficient procedure for multiplying large numbers ** Schönhage–Strassen algorithm: an asymptotically fast multiplication algorithm for large integers ** Toom–Cook multiplication: (Toom3) a multiplication algorithm for large integers * Multiplicative inverse Algorithms: for computing a number's multiplicative inverse (reciprocal). **
Newton's method In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real ...
* Rounding functions: the classic ways to round numbers * Spigot algorithm: a way to compute the value of a
mathematical constant A mathematical constant is a key number whose value is fixed by an unambiguous definition, often referred to by a symbol (e.g., an alphabet letter), or by mathematicians' names to facilitate using it across multiple mathematical problems. Cons ...
without knowing preceding digits * Square and Nth root of a number: ** Alpha max plus beta min algorithm: an approximation of the square-root of the sum of two squares ** Methods of computing square roots ** ''n''th root algorithm ** Shifting nth-root algorithm: digit by digit root extraction * Summation: ** Binary splitting: a
divide and conquer Divide and rule policy ( la, divide et impera), or divide and conquer, in politics and sociology is gaining and maintaining power divisively. Historically, this strategy was used in many different ways by empires seeking to expand their terr ...
technique which speeds up the numerical evaluation of many types of series with rational terms ** Kahan summation algorithm: a more accurate method of summing floating-point numbers * Unrestricted algorithm


Geometric

* Filtered back-projection: efficiently computes the inverse 2-dimensional
Radon transform In mathematics, the Radon transform is the integral transform which takes a function ''f'' defined on the plane to a function ''Rf'' defined on the (two-dimensional) space of lines in the plane, whose value at a particular line is equal to the ...
. * Level set method (LSM): a numerical technique for tracking interfaces and shapes


Interpolation and extrapolation

* Birkhoff interpolation: an extension of polynomial interpolation * Cubic interpolation * Hermite interpolation *
Lagrange interpolation In numerical analysis, the Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data. Given a data set of coordinate pairs (x_j, y_j) with 0 \leq j \leq k, the x_j are called ''nodes'' an ...
: interpolation using
Lagrange polynomial In numerical analysis, the Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data. Given a data set of coordinate pairs (x_j, y_j) with 0 \leq j \leq k, the x_j are called ''nodes'' an ...
s *
Linear interpolation In mathematics, linear interpolation is a method of curve fitting using linear polynomials to construct new data points within the range of a discrete set of known data points. Linear interpolation between two known points If the two known po ...
: a method of curve fitting using linear polynomials *
Monotone cubic interpolation In the mathematical field of numerical analysis, monotone cubic interpolation is a variant of cubic interpolation that preserves monotonicity of the data set being interpolated. Monotonicity is preserved by linear interpolation but not guarante ...
: a variant of cubic interpolation that preserves monotonicity of the data set being interpolated. *
Multivariate interpolation In numerical analysis, multivariate interpolation is interpolation on functions of more than one variable; when the variates are spatial coordinates, it is also known as spatial interpolation. The function to be interpolated is known at given po ...
** Bicubic interpolation, a generalization of cubic interpolation to two dimensions **
Bilinear interpolation In mathematics, bilinear interpolation is a method for interpolating functions of two variables (e.g., ''x'' and ''y'') using repeated linear interpolation. It is usually applied to functions sampled on a 2D rectilinear grid, though it can be ge ...
: an extension of
linear interpolation In mathematics, linear interpolation is a method of curve fitting using linear polynomials to construct new data points within the range of a discrete set of known data points. Linear interpolation between two known points If the two known po ...
for interpolating functions of two variables on a regular grid ** Lanczos resampling ("Lanzosh"): a multivariate interpolation method used to compute new values for any digitally sampled data ** Nearest-neighbor interpolation ** Tricubic interpolation, a generalization of cubic interpolation to three dimensions * Pareto interpolation: a method of estimating the median and other properties of a population that follows a
Pareto distribution The Pareto distribution, named after the Italian civil engineer, economist, and sociologist Vilfredo Pareto ( ), is a power-law probability distribution that is used in description of social, quality control, scientific, geophysical, actu ...
. *
Polynomial interpolation In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset. Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with n ...
**
Neville's algorithm In mathematics, Neville's algorithm is an algorithm used for polynomial interpolation that was derived by the mathematician Eric Harold Neville in 1934. Given ''n'' + 1 points, there is a unique polynomial of degree ''≤ n'' which goes through the ...
*
Spline interpolation In the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. That is, instead of fitting a single, high-degree polynomial to all ...
: Reduces error with
Runge's phenomenon In the mathematical field of numerical analysis, Runge's phenomenon () is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree over a set of equispaced interpolation ...
. ** De Boor algorithm:
B-spline In the mathematical subfield of numerical analysis, a B-spline or basis spline is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. Any spline function of given degree can be expresse ...
s ** De Casteljau's algorithm: Bézier curves * Trigonometric interpolation


Linear algebra

* Eigenvalue algorithms ** Arnoldi iteration **
Inverse iteration In numerical analysis, inverse iteration (also known as the ''inverse power method'') is an iterative eigenvalue algorithm. It allows one to find an approximate eigenvector when an approximation to a corresponding eigenvalue is already known. The me ...
** Jacobi method ** Lanczos iteration ** Power iteration ** QR algorithm **
Rayleigh quotient iteration Rayleigh quotient iteration is an eigenvalue algorithm which extends the idea of the inverse iteration by using the Rayleigh quotient to obtain increasingly accurate eigenvalue estimates. Rayleigh quotient iteration is an iterative method, tha ...
* Gram–Schmidt process: orthogonalizes a set of vectors * Matrix multiplication algorithms ** Cannon's algorithm: a distributed algorithm for matrix multiplication especially suitable for computers laid out in an N × N mesh ** Coppersmith–Winograd algorithm: square matrix multiplication ** Freivalds' algorithm: a randomized algorithm used to verify matrix multiplication ** Strassen algorithm: faster matrix multiplication * Solving system of linear equations, systems of linear equations ** Biconjugate gradient method: solves systems of linear equations ** Conjugate gradient: an algorithm for the numerical solution of particular systems of linear equations ** Gaussian elimination ** Gauss–Jordan elimination: solves systems of linear equations ** Gauss–Seidel method: solves systems of linear equations iteratively ** Levinson recursion: solves equation involving a Toeplitz matrix ** Stone's method: also known as the strongly implicit procedure or SIP, is an algorithm for solving a sparse linear system of equations ** Successive over-relaxation (SOR): method used to speed up convergence of the Gauss–Seidel method ** Tridiagonal matrix algorithm (Thomas algorithm): solves systems of tridiagonal equations * Sparse matrix algorithms ** Cuthill–McKee algorithm: reduce the bandwidth (matrix theory), bandwidth of a symmetric sparse matrix ** Minimum degree algorithm: permute the rows and columns of a symmetric sparse matrix before applying the Cholesky decomposition ** Symbolic Cholesky decomposition: Efficient way of storing sparse matrix


Monte Carlo

* Gibbs sampling: generates a sequence of samples from the joint probability distribution of two or more random variables * Hybrid Monte Carlo: generates a sequence of samples using Hamiltonian dynamics, Hamiltonian weighted Markov chain Monte Carlo, from a probability distribution which is difficult to sample directly. * Metropolis–Hastings algorithm: used to generate a sequence of samples from the probability distribution of one or more variables * Wang and Landau algorithm: an extension of Metropolis–Hastings algorithm sampling


Numerical integration

* MISER algorithm: Monte Carlo simulation, numerical integration


Root finding

* Bisection method * False position method: approximates roots of a function * ITP Method, ITP method: minmax optimal and superlinar convergence simultaneously *
Newton's method In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real ...
: finds zeros of functions with calculus * Halley's method: uses first and second derivatives * Secant method: 2-point, 1-sided * False position method and Illinois method: 2-point, bracketing * Ridder's method: 3-point, exponential scaling * Muller's method: 3-point, quadratic interpolation


Optimization algorithms

* Alpha–beta pruning: search to reduce number of nodes in minimax algorithm * Branch and bound * Bruss algorithm: see odds algorithm * Chain matrix multiplication * Combinatorial optimization: optimization problems where the set of feasible solutions is discrete ** Greedy randomized adaptive search procedure (GRASP): successive constructions of a greedy randomized solution and subsequent iterative improvements of it through a local search ** Hungarian method: a combinatorial optimization algorithm which solves the assignment problem in polynomial time * Constraint satisfaction ** General algorithms for the constraint satisfaction *** AC-3 algorithm *** Difference map algorithm *** Min conflicts algorithm ** Chaff algorithm: an algorithm for solving instances of the boolean satisfiability problem ** Davis–Putnam algorithm: check the validity of a first-order logic formula ** DPLL algorithm, Davis–Putnam–Logemann–Loveland algorithm (DPLL): an algorithm for deciding the satisfiability of propositional logic formula in conjunctive normal form, i.e. for solving the CNF-SAT problem ** Exact cover problem *** Algorithm X: a nondeterministic algorithm *** Dancing Links: an efficient implementation of Algorithm X * Cross-entropy method: a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling * Differential evolution * Dynamic Programming: problems exhibiting the properties of overlapping subproblems and optimal substructure * Ellipsoid method: is an algorithm for solving convex optimization problems * Evolutionary computation: optimization inspired by biological mechanisms of evolution ** Evolution strategy ** Gene expression programming ** Genetic algorithms *** Fitness proportionate selection – also known as roulette-wheel selection *** Stochastic universal sampling *** Truncation selection *** Tournament selection ** Memetic algorithm ** Swarm intelligence *** Ant colony optimization *** Bees algorithm: a search algorithm which mimics the food foraging behavior of swarms of honey bees *** Particle swarm optimization, Particle swarm * Frank-Wolfe algorithm: an iterative first-order optimization algorithm for constrained convex optimization * Golden-section search: an algorithm for finding the maximum of a real function * Gradient descent * Hyperparameter optimization#Grid search, Grid Search * Harmony search (HS): a metaheuristic algorithm mimicking the improvisation process of musicians * Interior point method * Linear programming ** Benson's algorithm: an algorithm for solving linear vector optimization problems ** Dantzig–Wolfe decomposition: an algorithm for solving linear programming problems with special structure ** Delayed column generation ** Integer linear programming: solve linear programming problems where some or all the unknowns are restricted to integer values *** Branch and cut *** Cutting-plane method ** Karmarkar's algorithm: The first reasonably efficient algorithm that solves the linear programming problem in polynomial time. ** Simplex algorithm: an algorithm for solving linear programming problems * Line search * Local search (optimization), Local search: a metaheuristic for solving computationally hard optimization problems ** Random-restart hill climbing ** Tabu search * Minimax#Minimax algorithm with alternate moves, Minimax used in game programming *
Nearest neighbor search Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function ...
(NNS): find closest points in a metric space ** Best Bin First: find an approximate solution to the nearest neighbor search problem in very-high-dimensional spaces * Newton's method in optimization * Nonlinear optimization ** BFGS method: a nonlinear optimization algorithm ** Gauss–Newton algorithm: an algorithm for solving nonlinear least squares problems ** Levenberg–Marquardt algorithm: an algorithm for solving nonlinear least squares problems ** Nelder–Mead method (downhill simplex method): a nonlinear optimization algorithm * Odds algorithm (Bruss algorithm): Finds the optimal strategy to predict a last specific event in a random sequence event * Hyperparameter optimization#Random search, Random Search * Simulated annealing * Stochastic tunneling * Subset sum problem, Subset sum algorithm


Computational science


Astronomy

* Doomsday algorithm: day of the week * Zeller's congruence is an algorithm to calculate the day of the week for any Julian or Gregorian calendar date * various Computus, Easter algorithms are used to calculate the day of Easter


Bioinformatics

* Basic Local Alignment Search Tool also known as BLAST: an algorithm for comparing primary biological sequence information * Kabsch algorithm: calculate the optimal alignment of two sets of points in order to compute the RMSD, root mean squared deviation between two protein structures. * Velvet (algorithm), Velvet: a set of algorithms manipulating de Bruijn graphs for genomic sequence assembly * Sorting by signed reversals: an algorithm for understanding genomic evolution. * Maximum parsimony (phylogenetics): an algorithm for finding the simplest phylogenetic tree to explain a given character matrix. * UPGMA: a distance-based phylogenetic tree construction algorithm.


Geoscience

* Vincenty's formulae: a fast algorithm to calculate the distance between two latitude/longitude points on an ellipsoid * Geohash: a public domain algorithm that encodes a decimal latitude/longitude pair as a hash string


Linguistics

* Lesk algorithm: word sense disambiguation * Stemming, Stemming algorithm: a method of reducing words to their stem, base, or root form * Sukhotin's algorithm: a statistical classification algorithm for classifying characters in a text as vowels or consonants


Medicine

* ESC algorithm for the diagnosis of heart failure * Manning Criteria for irritable bowel syndrome * Pulmonary embolism#Algorithms, Pulmonary embolism diagnostic algorithms * Texas Medication Algorithm Project


Physics

* Constraint algorithm: a class of algorithms for satisfying constraints for bodies that obey Newton's equations of motion * Demon algorithm: a Monte Carlo method for efficiently sampling members of a microcanonical ensemble with a given energy * Featherstone's algorithm: computes the effects of forces applied to a structure of joints and links * Ground state approximation ** Variational method *** Ritz method * N-body problem, ''n''-body problems ** Barnes–Hut simulation: Solves the n-body problem in an approximate way that has the order instead of as in a direct-sum simulation. ** Fast multipole method (FMM): speeds up the calculation of long-ranged forces * Rainflow-counting algorithm: Reduces a complex stress (physics), stress history to a count of elementary stress-reversals for use in fatigue (material), fatigue analysis * Sweep and prune: a broad phase algorithm used during collision detection to limit the number of pairs of solids that need to be checked for collision * VEGAS algorithm: a method for reducing error in Monte Carlo simulations * Glauber dynamics: a method for simulating the Ising Model on a computer


Statistics

* Algorithms for calculating variance: avoiding instability and numerical overflow * Approximate counting algorithm: allows counting large number of events in a small register * Bayesian statistics ** Nested sampling algorithm: a computational approach to the problem of comparing models in Bayesian statistics * Data clustering, Clustering Algorithms ** UPGMA, Average-linkage clustering: a simple agglomerative clustering algorithm ** Canopy clustering algorithm: an unsupervised pre-clustering algorithm related to the K-means algorithm ** Complete-linkage clustering: a simple agglomerative clustering algorithm ** DBSCAN: a density based clustering algorithm ** Expectation-maximization algorithm ** Fuzzy clustering: a class of clustering algorithms where each point has a degree of belonging to clusters *** Fuzzy clustering#Fuzzy c-means clustering, Fuzzy c-means *** FLAME clustering (Fuzzy clustering by Local Approximation of MEmberships): define clusters in the dense parts of a dataset and perform cluster assignment solely based on the neighborhood relationships among objects ** KHOPCA clustering algorithm: a local clustering algorithm, which produces hierarchical multi-hop clusters in static and mobile environments. ** k-means clustering: cluster objects based on attributes into partitions ** k-means++: a variation of this, using modified random seeds ** k-medoids: similar to k-means, but chooses datapoints or medoids as centers ** Linde–Buzo–Gray algorithm: a vector quantization algorithm to derive a good codebook ** Lloyd's algorithm (Voronoi iteration or relaxation): group data points into a given number of categories, a popular algorithm for k-means clustering ** OPTICS algorithm, OPTICS: a density based clustering algorithm with a visual evaluation method ** Single-linkage clustering: a simple agglomerative clustering algorithm ** SUBCLU: a subspace clustering algorithm ** Ward's method: an agglomerative clustering algorithm, extended to more general Lance–Williams algorithms ** WACA clustering algorithm: a local clustering algorithm with potentially multi-hop structures; for dynamic networks * Estimation theory, Estimation Theory ** Expectation-maximization algorithm A class of related algorithms for finding maximum likelihood estimates of parameters in probabilistic models *** Ordered subset expectation maximization (OSEM): used in medical imaging for positron emission tomography, single-photon emission computed tomography and X-ray computed tomography. ** Odds algorithm (Bruss algorithm) Optimal online search for distinguished value in sequential random input ** Kalman filter: estimate the state of a linear Dynamical system, dynamic system from a series of noisy measurements * False nearest neighbor algorithm (FNN) estimates fractal dimension * Hidden Markov model ** Baum–Welch algorithm: computes maximum likelihood estimates and Maximum a posteriori, posterior mode estimates for the parameters of a hidden Markov model ** Forward-backward algorithm: a dynamic programming algorithm for computing the probability of a particular observation sequence ** Viterbi algorithm: find the most likely sequence of hidden states in a hidden Markov model * Partial least squares regression: finds a linear model describing some predicted variables in terms of other observable variables * Queuing theory ** Buzen's algorithm: an algorithm for calculating the normalization constant G(K) in the Gordon–Newell theorem * RANSAC (an abbreviation for "RANdom SAmple Consensus"): an iterative method to estimate parameters of a mathematical model from a set of observed data which contains outliers * Scoring algorithm: is a form of
Newton's method In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real ...
used to solve maximum likelihood equations numerically * Yamartino method: calculate an approximation to the standard deviation σθ of wind direction θ during a single pass through the incoming data * Ziggurat algorithm: generates random numbers from a non-uniform distribution


Computer science


Computer architecture

* Tomasulo algorithm: allows sequential instructions that would normally be stalled due to certain dependencies to execute non-sequentially


Computer graphics

* Clipping (computer graphics), Clipping ** Line clipping *** Cohen–Sutherland *** Cyrus–Beck *** Fast clipping, Fast-clipping *** Liang–Barsky algorithm, Liang–Barsky *** Nicholl–Lee–Nicholl ** Polygon clipping *** Sutherland–Hodgman *** Vatti clipping algorithm, Vatti *** Weiler–Atherton * Contour lines and Isosurfaces ** Marching cubes: extract a polygonal mesh of an isosurface from a three-dimensional scalar field (sometimes called voxels) ** Marching squares: generates contour lines for a two-dimensional scalar field ** Marching tetrahedrons: an alternative to Marching cubes * Discrete Green's Theorem: is an algorithm for computing double integral over a generalized rectangular domain in constant time. It is a natural extension to the summed area table algorithm * Flood fill: fills a connected region of a multi-dimensional array with a specified symbol * Global illumination algorithms: Considers direct illumination and reflection from other objects. ** Ambient occlusion ** Beam tracing ** Cone tracing ** Image-based lighting ** Metropolis light transport ** Path tracing ** Photon mapping ** Radiosity (3D computer graphics), Radiosity ** Ray tracing (graphics), Ray tracing * Hidden-surface determination, Hidden-surface removal or Hidden-surface determination, Visual surface determination ** Newell's algorithm: eliminate polygon cycles in the depth sorting required in hidden-surface removal ** Painter's algorithm: detects visible parts of a 3-dimensional scenery ** Scanline rendering: constructs an image by moving an imaginary line over the image ** Warnock algorithm * Line drawing algorithm, Line Drawing: graphical algorithm for approximating a line segment on discrete graphical media. ** Bresenham's line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses decision variables) ** Digital Differential Analyzer (graphics algorithm), DDA line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses floating-point math) ** Xiaolin Wu's line algorithm: algorithm for line antialiasing. * Midpoint circle algorithm: an algorithm used to determine the points needed for drawing a circle * Ramer–Douglas–Peucker algorithm: Given a 'curve' composed of line segments to find a curve not too dissimilar but that has fewer points * Shading ** Gouraud shading: an algorithm to simulate the differing effects of light and colour across the surface of an object in 3D computer graphics ** Phong shading: an algorithm to interpolate surface normal-vectors for surface shading in 3D computer graphics * Slerp (spherical linear interpolation): quaternion interpolation for the purpose of animating 3D rotation * Summed area table (also known as an integral image): an algorithm for computing the sum of values in a rectangular subset of a grid in constant time


Cryptography

* Asymmetric key algorithm, Asymmetric (public key) encryption: ** ElGamal encryption, ElGamal ** Elliptic curve cryptography ** Matei Array Encreption 1, MAE1 ** NTRUEncrypt ** RSA (cryptosystem), RSA * Digital signatures (asymmetric authentication): ** Digital Signature Algorithm, DSA, and its variants: *** ECDSA an
Deterministic ECDSA
*** EdDSA (Ed25519) ** RSA (cryptosystem), RSA * Cryptographic hash functions (see also the section on message authentication codes): ** BLAKE (hash function), BLAKE ** MD5 – Note that there is now a method of generating collisions for MD5 ** RIPEMD-160 ** SHA-1 – Note that there is now a method of generating collisions for SHA-1 ** SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) ** SHA-3 (SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256) ** Tiger (hash function), Tiger (TTH), usually used in Hash tree (persistent data structure), Tiger tree hashes ** WHIRLPOOL * Cryptographically secure pseudo-random number generators ** Blum Blum Shub – based on the hardness of integer factorization, factorization ** Fortuna (PRNG), Fortuna, intended as an improvement on Yarrow algorithm ** Linear-feedback shift register (note: many LFSR-based algorithms are weak or have been broken) ** Yarrow algorithm * Key exchange ** Diffie–Hellman key exchange ** Elliptic-curve Diffie–Hellman (ECDH) * Key derivation functions, often used for password hashing and key stretching ** bcrypt ** PBKDF2 ** scrypt ** Argon2 * Message authentication codes (symmetric authentication algorithms, which take a key as a parameter): ** keyed-hash message authentication code, HMAC: keyed-hash message authentication ** Poly1305 ** SipHash * Secret sharing, Secret Splitting, Key Splitting, M of N algorithms ** Blakey's Scheme ** Shamir's Secret Sharing, Shamir's Scheme * symmetric key algorithm, Symmetric (secret key) encryption: ** Advanced Encryption Standard (AES), winner of NIST competition, also known as Rijndael ** Blowfish (cipher), Blowfish ** Twofish ** Threefish ** Data Encryption Standard (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes ** International Data Encryption Algorithm, IDEA ** RC4 (cipher) ** Tiny Encryption Algorithm (TEA) ** Salsa20, and its updated variant Salsa20#ChaCha variant, ChaCha20 * Post-quantum cryptography * Proof-of-work system, Proof-of-work algorithms


Digital logic

* Boolean minimization ** Quine–McCluskey algorithm: also called as Q-M algorithm, programmable method for simplifying the boolean equations ** Petrick's method: another algorithm for boolean simplification ** Espresso heuristic logic minimizer: a fast algorithm for boolean function minimization


Machine learning and statistical classification

* ALOPEX: a correlation-based Machine learning, machine-learning algorithm * Association rule learning: discover interesting relations between variables, used in data mining ** Apriori algorithm ** Eclat algorithm ** Association rule learning#FP-growth algorithm, FP-growth algorithm ** One-attribute rule ** Association rule learning#Zero-attribute rule, Zero-attribute rule * Boosting (meta-algorithm): Use many weak learners to boost effectiveness ** AdaBoost: adaptive boosting ** BrownBoost: a boosting algorithm that may be robust to noisy datasets ** LogitBoost: logistic regression boosting ** LPBoost: linear programming boosting * Bootstrap aggregating (bagging): technique to improve stability and classification accuracy * Computer Vision ** Grabcut based on Graph cuts in computer vision, Graph cuts * Decision tree learning, Decision Trees ** C4.5 algorithm: an extension to ID3 ** ID3 algorithm (Iterative Dichotomiser 3): use heuristic to generate small decision trees * Cluster analysis, Clustering: a class of unsupervised learning algorithms for grouping and bucketing related input vector. ** k-nearest neighbors (k-NN): a method for classifying objects based on closest training examples in the feature space * Linde–Buzo–Gray algorithm: a vector quantization algorithm used to derive a good codebook * Locality-sensitive hashing (LSH): a method of performing probabilistic dimension reduction of high-dimensional data * Artificial neural network, Neural Network ** Backpropagation: a supervised learning method which requires a teacher that knows, or can calculate, the desired output for any given input ** Hopfield net: a Recurrent neural network in which all connections are symmetric ** Perceptron: the simplest kind of feedforward neural network: a linear classifier. ** Pulse-coupled neural networks (PCNN): Artificial neural network, Neural models proposed by modeling a cat's visual cortex and developed for high-performance Bionics, biomimetic image processing. ** Radial basis function network: an artificial neural network that uses radial basis functions as activation functions ** Self-organizing map: an unsupervised network that produces a low-dimensional representation of the input space of the training samples * Random forest: classify using many decision trees * Reinforcement learning: ** Q-learning: learns an action-value function that gives the expected utility of taking a given action in a given state and following a fixed policy thereafter ** State–action–reward–state–action, State–Action–Reward–State–Action (SARSA): learn a Markov decision process policy ** Temporal difference learning * relevance vector machine, Relevance-Vector Machine (RVM): similar to SVM, but provides probabilistic classification * Supervised learning: Learning by examples (labelled data-set split into training-set and test-set) * Support vector machine, Support Vector Machine (SVM): a set of methods which divide multidimensional data by finding a dividing hyperplane with the maximum margin between the two sets ** Structured SVM: allows training of a classifier for general structured output labels. * Winnow algorithm: related to the perceptron, but uses a Multiplicative Weight Update Method, multiplicative weight-update scheme


Programming language theory

* C3 linearization: an algorithm used primarily to obtain a consistent linearization of a multiple inheritance hierarchy in object-oriented programming * Chaitin's algorithm: a bottom-up, graph coloring register allocation algorithm that uses cost/degree as its spill metric * Hindley-Milner type inference, Hindley–Milner type inference algorithm * Rete algorithm: an efficient pattern matching algorithm for implementing Start symbol (formal languages), production rule systems * Sethi-Ullman algorithm: generates optimal code for arithmetic expressions


Parsing

* CYK algorithm: an O(n3) algorithm for parsing context-free grammars in Chomsky normal form * Earley parser: another O(n3) algorithm for parsing any context-free grammar * GLR parser: an algorithm for parsing any context-free grammar by Masaru Tomita. It is tuned for deterministic grammars, on which it performs almost linear time and O(n3) in worst case. * Inside-outside algorithm: an O(n3) algorithm for re-estimating production probabilities in probabilistic context-free grammars * LL parser: a relatively simple linear time parsing algorithm for a limited class of context-free grammars * LR parser: A more complex linear time parsing algorithm for a larger class of context-free grammars. Variants: ** Canonical LR parser ** Look-ahead LR parser, LALR (look-ahead LR) parser ** Operator-precedence parser ** Simple LR parser, SLR (Simple LR) parser ** Simple precedence parser * Packrat parser: a linear time parsing algorithm supporting some context-free grammars and parsing expression grammars * Recursive descent parser: a top-down parsing, top-down parser suitable for LL(''k'') grammars * Shunting-yard algorithm: converts an infix-notation math expression to postfix * Pratt parser * Lexical analysis


Quantum algorithms

* Deutsch–Jozsa algorithm: criterion of balance for Boolean function * Grover's algorithm: provides quadratic speedup for many search problems *
Shor's algorithm Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. On a quantum computer, to factor an integer N , Shor's algorithm runs in polynomial ...
: provides exponential function, exponential speedup (relative to currently known non-quantum algorithms) for factoring a number * Simon's algorithm: provides a provably exponential function, exponential speedup (relative to any non-quantum algorithm) for a black-box problem


Theory of computation and automata

* DFA minimization#Hopcroft's algorithm, Hopcroft's algorithm, DFA minimization#Moore's algorithm, Moore's algorithm, and DFA minimization#Brzozowski's algorithm, Brzozowski's algorithm: algorithms for DFA minimization, minimizing the number of states in a deterministic finite automaton * Powerset construction: algorithm to convert nondeterministic automaton to deterministic automaton. * Tarski–Kuratowski algorithm: a non-deterministic algorithm which provides an upper bound for the complexity of formulas in the arithmetical hierarchy and analytical hierarchy


Information theory and signal processing


Coding theory


Error detection and correction

* BCH Codes ** Berlekamp–Massey algorithm ** Peterson–Gorenstein–Zierler algorithm ** Reed–Solomon error correction * BCJR algorithm: decoding of error correcting codes defined on trellises (principally convolutional codes) * Forward error correction * Gray code * Hamming codes ** Hamming(7,4): a Hamming code that encodes 4 bits of data into 7 bits by adding 3 parity bits **
Hamming distance In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chang ...
: sum number of positions which are different ** Hamming weight (population count): find the number of 1 bits in a binary word * Redundancy checks ** Adler-32 ** Cyclic redundancy check ** Damm algorithm ** Fletcher's checksum ** Longitudinal redundancy check (LRC) ** Luhn algorithm: a method of validating identification numbers ** Luhn mod N algorithm: extension of Luhn to non-numeric characters ** Parity bit, Parity: simple/fast error detection technique ** Verhoeff algorithm


Lossless compression algorithms

* Burrows–Wheeler transform: preprocessing useful for improving Lossless data compression, lossless compression * Context tree weighting * Delta encoding: aid to compression of data in which sequential data occurs frequently * Dynamic Markov compression: Compression using predictive arithmetic coding * Dictionary coders ** Byte pair encoding (BPE) ** Deflate ** Lempel–Ziv *** LZ77 and LZ78 *** LZJB, Lempel–Ziv Jeff Bonwick (LZJB) *** Lempel–Ziv–Markov chain algorithm (LZMA) *** Lempel–Ziv–Oberhumer (LZO): speed oriented *** Lempel–Ziv–Stac (LZS) *** Lempel–Ziv–Storer–Szymanski (LZSS) *** Lempel–Ziv–Welch (LZW) *** LZWL: syllable-based variant *** LZX *** LZRW, Lempel–Ziv Ross Williams (LZRW) * Entropy encoding: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols ** Arithmetic coding: advanced entropy coding *** Range encoding: same as arithmetic coding, but looked at in a slightly different way ** Huffman coding: simple lossless compression taking advantage of relative character frequencies *** Adaptive Huffman coding: adaptive coding technique based on Huffman coding *** Package-merge algorithm: Optimizes Huffman coding subject to a length restriction on code strings ** Shannon–Fano coding ** Shannon–Fano–Elias coding: precursor to arithmetic encoding * Entropy encoding, Entropy coding with known entropy characteristics ** Golomb coding: form of entropy coding that is optimal for alphabets following geometric distributions ** Rice coding: form of entropy coding that is optimal for alphabets following geometric distributions ** Truncated binary encoding ** Unary coding: code that represents a number n with n ones followed by a zero ** Universal code (data compression), Universal codes: encodes positive integers into binary code words *** Elias Elias delta coding, delta, Elias gamma coding, gamma, and Elias omega coding, omega coding *** Exponential-Golomb coding *** Fibonacci coding *** Levenshtein coding * FELICS, Fast Efficient & Lossless Image Compression System (FELICS): a lossless image compression algorithm * Incremental encoding: delta encoding applied to sequences of strings * PPM compression algorithm, Prediction by partial matching (PPM): an adaptive statistical data compression technique based on context modeling and prediction * Run-length encoding: lossless data compression taking advantage of strings of repeated characters * SEQUITUR algorithm: lossless compression by incremental grammar inference on a string


Lossy compression algorithms

* 3Dc: a lossy data compression algorithm for Normal mapping, normal maps * Audio data compression, Audio and speech encoding, Speech compression ** A-law algorithm: standard companding algorithm ** Code-excited linear prediction (CELP): low bit-rate speech compression ** Linear predictive coding (LPC): lossy compression by representing the spectral envelope of a digital signal of speech in compressed form ** Mu-law algorithm: standard analog signal compression or companding algorithm ** Warped Linear Predictive Coding (WLPC) * Image compression ** Block Truncation Coding (BTC): a type of lossy image compression technique for greyscale images ** Embedded Zerotree Wavelet (EZW) ** Fast Cosine Transform, Fast Cosine Transform algorithms (FCT algorithms): computes Discrete Cosine Transform (DCT) efficiently ** Fractal compression: method used to compress images using fractals ** Set Partitioning in Hierarchical Trees (SPIHT) ** Wavelet compression: form of data compression well suited for image compression (sometimes also video compression and audio compression) * Transform coding: type of data compression for "natural" data like audio signals or photographic images * Video compression * Vector quantization: technique often used in lossy data compression


Digital signal processing

* Adaptive-additive algorithm (AA algorithm): find the spatial frequency phase of an observed wave source * Discrete Fourier transform: determines the frequencies contained in a (segment of a) signal ** Bluestein's FFT algorithm ** Bruun's FFT algorithm ** Cooley–Tukey FFT algorithm ** Fast Fourier transform ** Prime-factor FFT algorithm ** Rader's FFT algorithm * Fast folding algorithm: an efficient algorithm for the detection of approximately periodic events within time series data * Gerchberg–Saxton algorithm: Phase retrieval algorithm for optical planes * Goertzel algorithm: identify a particular frequency component in a signal. Can be used for DTMF digit decoding. * Karplus-Strong string synthesis: physical modelling synthesis to simulate the sound of a hammered or plucked string or some types of percussion


Image processing

* Contrast Enhancement ** Histogram equalization: use histogram to improve image contrast ** Adaptive histogram equalization: histogram equalization which adapts to local changes in contrast * Connected-component labeling: find and label disjoint regions * Dithering and half-toning ** Error diffusion ** Floyd–Steinberg dithering ** Ordered dithering ** Riemersma dithering * Elser difference-map algorithm: a search algorithm for general constraint satisfaction problems. Originally used for X-ray crystallography, X-Ray diffraction microscopy * Feature detection (computer vision), Feature detection ** Canny edge detector: detect a wide range of edges in images ** Generalised Hough transform ** Hough transform ** Marr–Hildreth algorithm: an early edge detection algorithm ** Scale-invariant feature transform, SIFT (Scale-invariant feature transform): is an algorithm to detect and describe local features in images. ** : is a robust local feature detector, first presented by Herbert Bay et al. in 2006, that can be used in computer vision tasks like object recognition or 3D reconstruction. It is partly inspired by the SIFT descriptor. The standard version of SURF is several times faster than SIFT and claimed by its authors to be more robust against different image transformations than SIFT. * Richardson–Lucy deconvolution: image de-blurring algorithm * Blind deconvolution: image de-blurring algorithm when point spread function is unknown. * Median filtering * Seam carving: content-aware image resizing algorithm * Segmentation (image processing), Segmentation: partition a digital image into two or more regions ** GrowCut algorithm: an interactive segmentation algorithm ** Random walker algorithm ** Region growing ** Watershed (algorithm), Watershed transformation: a class of algorithms based on the watershed analogy


Software engineering

* Cache algorithms * CHS conversion: converting between disk addressing systems * Double dabble: Convert binary numbers to BCD * Hash Function: convert a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index into an array ** Fowler–Noll–Vo hash function: fast with low collision rate ** Pearson hashing: computes 8 bit value only, optimized for 8 bit computers ** Zobrist hashing: used in the implementation of transposition tables * Unicode Collation Algorithm * Xor swap algorithm: swaps the values of two variables without using a buffer


Database algorithms

* Algorithms for Recovery and Isolation Exploiting Semantics (ARIES): transaction (database), transaction recovery * Join (SQL), Join algorithms ** Block nested loop ** Hash join ** Nested loop join ** Sort-Merge Join


Distributed systems algorithms

* Clock synchronization ** Berkeley algorithm ** Cristian's algorithm ** Intersection algorithm ** Marzullo's algorithm * Consensus (computer science): agreeing on a single value or history among unreliable processors ** Chandra–Toueg consensus algorithm ** Paxos algorithm ** Raft (computer science) * Detection of Process Termination ** Dijkstra-Scholten algorithm ** Huang's algorithm * Lamport ordering: a partial ordering of events based on the ''happened-before'' relation * Leader election: a method for dynamically selecting a coordinator ** Bully algorithm * Mutual exclusion ** Lamport's Distributed Mutual Exclusion Algorithm ** Naimi-Trehel's log(n) Algorithm ** Maekawa's algorithm, Maekawa's Algorithm ** Raymond's algorithm, Raymond's Algorithm ** Ricart–Agrawala algorithm, Ricart–Agrawala Algorithm * Snapshot algorithm: record a consistent global state for an asynchronous system ** Chandy–Lamport algorithm * Vector clocks: generate a partial ordering of events in a distributed system and detect causality violations


Memory allocation and deallocation algorithms

* Buddy memory allocation: an algorithm to allocate memory such with less fragmentation * Garbage collection (computer science), Garbage collectors ** Cheney's algorithm: an improvement on the Semi-space collector ** garbage collection (computer science), Generational garbage collector: Fast garbage collectors that segregate memory by age ** Mark-compact algorithm: a combination of the Mark and sweep, mark-sweep algorithm and Cheney's algorithm, Cheney's copying algorithm ** Mark and sweep ** Semi-space collector: an early copying collector * Reference counting


Networking

* Karn's algorithm: addresses the problem of getting accurate estimates of the round-trip time for messages when using TCP * Luleå algorithm: a technique for storing and searching internet routing tables efficiently * Network congestion ** Exponential backoff ** Nagle's algorithm: improve the efficiency of TCP/IP networks by coalescing packets ** Truncated binary exponential backoff


Operating systems algorithms

* Banker's algorithm: algorithm used for deadlock avoidance * Page replacement algorithms: for selecting the victim page under low memory conditions ** Adaptive replacement cache: better performance than LRU ** Clock with Adaptive Replacement (CAR): a page replacement algorithm with performance comparable to adaptive replacement cache


Process synchronization

* Dekker's algorithm * Lamport's Bakery algorithm * Peterson's algorithm


Scheduling

* Earliest deadline first scheduling * Fair-share scheduling * Least slack time scheduling * List scheduling * Multi level feedback queue * Rate-monotonic scheduling * Round-robin scheduling * Shortest job next * Shortest remaining time * Top-nodes algorithm: resource calendar management


I/O scheduling


Disk scheduling

* Elevator algorithm: Disk scheduling algorithm that works like an elevator. * Shortest seek first: Disk scheduling algorithm to reduce seek time.


Other

*'For You' algorithm: a proprietary algorithm developed by the social media network TikTok, Tik-Tok. Uploaded videos are released first to a selection of users who have been identified by the algorithm as being likely to engage with the video, based on their previous web-site viewing patterns.TikTok Finally Explains How the ‘For You’ Algorithm Works
''Wired'', published 18 June 2020, accessed 30 January 2022


See also

* List of data structures * List of machine learning algorithms * List of pathfinding algorithms * List of algorithm general topics * List of terms relating to algorithms and data structures * Heuristic


References

{{Reflist Algorithms, * Mathematics-related lists, Algorithms Optimization algorithms and methods,