An
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
is fundamentally a set of rules or defined procedures that is typically designed and used to solve a specific problem or a broad set of problems.
Broadly, algorithms define process(es), sets of rules, or methodologies that are to be followed in calculations, data processing, data mining, pattern recognition, automated reasoning or other problem-solving operations. With the increasing automation of services, more and more decisions are being made by algorithms. Some general examples are; risk assessments, anticipatory policing, and pattern recognition technology.
The following is a list of well-known algorithms.
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: solves the
stable matching 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 number generation, random n ...
s (uniformly distributed—see also
List of pseudorandom number generators
Random number generation, Random number generators are important in many kinds of technical applications, including physics, engineering or Mathematics, mathematical computer studies (e.g., Monte Carlo method, Monte Carlo simulations), cryptograph ...
for other PRNGs with varying degrees of convergence and varying statistical quality):
**
ACORN generator
**
Blum Blum Shub
**
Lagged Fibonacci generator A Lagged Fibonacci generator (LFG or sometimes LFib) is an example of a pseudorandom number generator. This class of random number generator is aimed at being an improvement on the 'standard' linear congruential generator. These are based on a gener ...
**
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 gener ...
**
Mersenne Twister
The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by and . Its name derives from the choice of a Mersenne prime as its period length.
The Mersenne Twister was created specifically to address most of ...
Graph algorithms
*
Coloring algorithm
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring ...
: Graph coloring algorithm.
*
Hopcroft–Karp algorithm: 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
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific ...
: 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 with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
*
Prüfer coding: conversion between a labeled tree and its
Prüfer sequence
*
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 (graph theory), tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and a ...
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
Spectral layout is a class of algorithm for drawing graphs. The layout uses the eigenvectors of a matrix, such as the Laplace matrix of the graph, as Cartesian coordinate
In geometry, a Cartesian coordinate system (, ) in a plane is a coor ...
Network theory
* Network analysis
** Link analysis
***
Girvan–Newman algorithm
The Girvan–Newman algorithm (named after Michelle Girvan and Mark Newman) is a hierarchical method used to detect communities in complex systems.Girvan M. and Newman M. E. J.Community structure in social and biological networks Proc. Natl. Acad. ...
: detect communities in complex systems
*** Web link analysis
****
Hyperlink-Induced Topic Search
Hyperlink-Induced Topic Search (HITS; also known as hubs and authorities) is a link analysis algorithm that rates Web pages, developed by Jon Kleinberg. The idea behind Hubs and Authorities stemmed from a particular insight into the creation of we ...
(HITS) (also known as
Hubs and authorities
Hyperlink-Induced Topic Search (HITS; also known as hubs and authorities) is a link analysis algorithm that rates Web pages, developed by Jon Kleinberg. The idea behind Hubs and Authorities stemmed from a particular insight into the creation of we ...
)
****
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. Accordin ...
****
TrustRank
TrustRank is an algorithm that conducts link analysis to separate useful webpages from spam and helps search engine rank pages in SERPs (Search Engine Results Pages). It is semi-automated process which means that it needs some human assistance i ...
*
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 Dinitz. The algorithm runs in O(, V, ^2, E, ) time ...
: is a
strongly polynomial
In computer science, a '' polynomial-time algorithm'' is generally speaking an algorithm whose running time is upper-bounded by some polynomial function of the input size. The definition naturally depends on the computational model, which determi ...
algorithm for computing the
maximum flow
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
The maximum flow problem can be seen as a special case of more complex network flow problems, such ...
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: implementation of Ford–Fulkerson
**
Ford–Fulkerson algorithm
The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a r ...
: computes the
maximum flow
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
The maximum flow problem can be seen as a special case of more complex network flow problems, such ...
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 optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
The maximum flow problem can be seen as a special case of more complex network flow problems, such ...
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 of maximum length in a given graph. A path is called ''simple'' if it does not have any repeated vertices; the length of a path may ...
: 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. ...
**
Borůvka's algorithm
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph,
or a minimum spanning forest in the case of a graph that is not connected.
It was first published in 1926 by Otakar Borůvka as a method of constructing an ...
**
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. It is a greedy algorithm that in each step adds to the forest the lowest-weight edge that ...
**
Prim's algorithm
In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a Weighted graph, weighted undirected graph. This means it finds a subset of the edge (graph theory), edges that forms a Tree (graph theory), tree ...
**
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 sa ...
*
Nonblocking minimal spanning switch say, for a
telephone exchange
A telephone exchange, telephone switch, or central office is a central component of a telecommunications system in the public switched telephone network (PSTN) or in large enterprises. It facilitates the establishment of communication circuits ...
*
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 (graph theory), vertex to all of the other vertices in a weighted digraph.
It is slower than Dijkstra's algorithm for the same problem, but more ...
: computes
shortest paths
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 ...
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 weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three ...
: computes
shortest paths
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 ...
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 po ...
: 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 homogeneous binary relation on a set (mathematics), set is the smallest Relation (mathematics), relation on that contains and is Transitive relation, transitive. For finite sets, "smallest" can be ...
problem: find the
transitive closure
In mathematics, the transitive closure of a homogeneous binary relation on a set (mathematics), set is the smallest Relation (mathematics), relation on that contains and is Transitive relation, transitive. For finite sets, "smallest" can be ...
of a given binary relation
*
Traveling salesman problem
In the theory of computational complexity, the travelling salesman problem (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 city exac ...
**
Christofides algorithm
**
Nearest neighbour algorithm
*
Vehicle routing problem
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises ...
** Clarke and Wright Saving 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 a modification of best-first search that reduces its memory requirements. Best-first searc ...
: is a heuristic search algorithm that is an optimization of
best-first search
Best-first search is a class of search algorithms which explores a graph by expanding the most promising node chosen according to a specified rule.
Judea Pearl described best-first search as estimating the promise of node ''n'' by a "heuristic eva ...
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 a modification of best-first search that reduces its memory requirements. Best-first searc ...
*
Best-first search
Best-first search is a class of search algorithms which explores a graph by expanding the most promising node chosen according to a specified rule.
Judea Pearl described best-first search as estimating the promise of node ''n'' by a "heuristic eva ...
: 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 (abstract data type), queue or stack (abstract data type), stack abstract data type.
In a priority queue, each element has an associated ''priority'', which ...
*
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 dept ...
: traverses a graph level by level
*
Brute-force search
In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of Iteration#Computing, systematically checking all possible candida ...
: an exhaustive and reliable search method, but computationally inefficient in many applications
*
D*: an
incremental heuristic search
Incremental heuristic search algorithms combine both incremental and heuristic search to speed up searches of sequences of similar search problems, which is important in domains that are only incompletely known or change dynamically. Incremental s ...
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 al ...
: traverses a graph branch by branch
*
Dijkstra's algorithm
Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three ...
: a special case of A* for which no heuristic function is used
*
General Problem Solver
General Problem Solver (GPS) is a computer program created in 1957 by Herbert A. Simon, J. C. Shaw, and Allen Newell ( RAND Corporation) intended to work as a universal problem solver machine. In contrast to the former Logic Theorist project, ...
: a seminal theorem-proving algorithm intended to work as a universal problem solver machine.
*
Iterative deepening depth-first search
In computer science, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with incre ...
(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
*
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. In ...
: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm
*
Uniform-cost search: 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
Subgraphs
*
Cliques
A clique ( AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardle ...
**
Bron–Kerbosch algorithm
In computer science, the Bron–Kerbosch algorithm is an enumeration algorithm for finding all maximal cliques in an undirected graph. That is, it lists all subsets of vertices with the two properties that each pair of vertices in one of the liste ...
: a technique for finding
maximal clique
In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of t ...
s in an undirected graph
**
MaxCliqueDyn maximum clique algorithm: find a
maximum clique in an undirected graph
*
Strongly connected components
**
Kosaraju's algorithm
**
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 ...
**
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 Kosaraj ...
*
Subgraph isomorphism problem
In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H.
Subgraph isomorphism is a gen ...
Sequence algorithms
Approximate sequence matching
*
Bitap algorithm: fuzzy algorithm that determines if strings are approximately equal.
*
Phonetic algorithm
A phonetic algorithm is an algorithm for indexing of words by their pronunciation. If the algorithm is based on orthography, it depends crucially on the spelling system of the language it is designed for: as most phonetic algorithms were developed ...
s
**
Daitch–Mokotoff Soundex: a
Soundex
Soundex is a phonetic algorithm for indexing names by sound, as pronounced in English. The goal is for homophones to be encoded to the same representation so that they can be matched despite minor differences in spelling. The algorithm mainly enc ...
refinement which allows matching of Slavic and Germanic surnames
**
Double Metaphone
Metaphone is a phonetic algorithm, published by Lawrence Philips in 1990, for indexing words by their English pronunciation. It fundamentally improves on the Soundex algorithm by using information about variations and inconsistencies in English s ...
: an improvement on Metaphone
**
Match rating approach: a phonetic algorithm developed by Western Airlines
**
Metaphone
Metaphone is a phonetic algorithm, published by Lawrence Philips in 1990, for indexing words by their English pronunciation. It fundamentally improves on the Soundex algorithm by using information about variations and inconsistencies in English s ...
: an algorithm for indexing words by their sound, when pronounced in English
**
NYSIIS:
phonetic algorithm
A phonetic algorithm is an algorithm for indexing of words by their pronunciation. If the algorithm is based on orthography, it depends crucially on the spelling system of the language it is designed for: as most phonetic algorithms were developed ...
, improves on
Soundex
Soundex is a phonetic algorithm for indexing names by sound, as pronounced in English. The goal is for homophones to be encoded to the same representation so that they can be matched despite minor differences in spelling. The algorithm mainly enc ...
**
Soundex
Soundex is a phonetic algorithm for indexing names by sound, as pronounced in English. The goal is for homophones to be encoded to the same representation so that they can be matched despite minor differences in spelling. The algorithm mainly enc ...
: 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 (mathematics), metric that measures distance ("inverse similarity") between two string (computer science), tex ...
s: computes a similarity or dissimilarity (distance) score between two pairs of text strings
**
Damerau–Levenshtein distance: 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
**
Hamming distance
In information theory, the Hamming distance between two String (computer science), strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number ...
: 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: search for text when the exact syntax or spelling of the target object is not precisely known
Selection algorithms
*
Introselect
In computer science, introselect (short for "introspective selection") is a selection algorithm that is a hybrid of quickselect and median of medians which has fast average performance and optimal worst-case performance. Introselect is related ...
*
Quickselect
In computer science, quickselect is a selection algorithm to find the ''k''th smallest element in an unordered list, also known as the ''k''th order statistic. Like the related quicksort sorting algorithm, it was developed by Tony Hoare, and t ...
Sequence search
*
Linear search
In computer science, 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 linea ...
: locates an item in an unsorted sequence
*
Selection algorithm
In computer science, a selection algorithm is an algorithm for finding the kth smallest value in a collection of ordered values, such as numbers. The value that it finds is called the order statistic. Selection includes as special cases the p ...
: finds the ''k''th largest item in a sequence
*
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
**
Eytzinger binary search
In computer science, multiplicative binary search is a variation
of binary search that uses a specific permutation of keys in an array instead of the sorted order used by regular binary
search.
Multiplicative binary search was first described by ...
: cache friendly binary search algorithm
**
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 sequence is a sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many writers begin the s ...
**
Jump search (or block search): linear search on a smaller subset of the sequence
**
Predictive search: binary-like search which factors in
magnitude
Magnitude may refer to:
Mathematics
*Euclidean vector, a quantity defined by both its magnitude and its direction
*Magnitude (mathematics), the relative size of an object
*Norm (mathematics), a term for the size or length of a vector
*Order of ...
of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search.
**
Uniform binary search: an optimization of the classic binary search algorithm
*
Ternary search
A ternary search algorithm is a technique in computer science for finding the minimum or maximum of a unimodal function.
The function
Assume we are looking for a maximum of f(x) and that we know the maximum lies somewhere between A and B. Fo ...
: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa
Sequence merging
*
k-way merge algorithm
In computer science, ''k''-way merge algorithms or multiway merges are a specific type of Merge algorithm, sequence merge algorithms that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms gen ...
* Simple 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
*
Heap's permutation generation algorithm: interchange elements to generate next permutation
*
Schensted algorithm: constructs a pair of
Young tableau
In mathematics, a Young tableau (; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups an ...
x 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. Eac ...
(also known as the Johnson–Trotter algorithm): generates permutations by transposing elements
Sequence combinations
Sequence alignment
*
Dynamic time warping
In time series analysis, dynamic time warping (DTW) is an algorithm for measuring similarity between two temporal sequences, which may vary in speed. For instance, similarities in walking could be detected using DTW, even if one person was walk ...
: measure similarity between two sequences which may vary in time or speed
*
Hirschberg's algorithm
In computer science, Hirschberg's algorithm, named after its inventor, Dan Hirschberg, is a dynamic programming algorithm that finds the optimal sequence alignment between two strings. Optimality is measured with the Levenshtein distance, define ...
: 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 biology, structural, or evolutionary relationships between ...
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, Swap (computer science), swapping their values ...
: 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 bu ...
or bidirectional bubble sort, a bubble sort traversing the list alternately from front to back and back to front
**
Comb sort
**
Gnome sort
**
Odd–even sort
In computing, an odd–even sort or odd–even transposition sort (also known as brick sort or parity sort) is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a compa ...
**
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 and stupid sort) is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It i ...
: the list is randomly shuffled until it happens to be sorted
**
Slowsort
**
Stalin sort
Joseph Vissarionovich Stalin (born Dzhugashvili; 5 March 1953) was a Soviet politician and revolutionary who led the Soviet Union from 1924 until his death in 1953. He held power as General Secretary of the Communist Party from 1922 to 1 ...
: all elements that are not in order are removed from the list
**
Stooge sort
* Hybrid
**
Flashsort
Flashsort is a distribution sorting algorithm showing linear computational complexity for uniformly distributed data sets and relatively little additional memory requirement. The original work was published in 1998 by Karl-Dietrich Neubert.
Co ...
**
Introsort
Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort, it switches to heapsort when the recursion depth exceeds a l ...
: 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 algo ...
: adaptative algorithm derived from merge sort and insertion sort. Used in Python 2.3 and up, and Java SE 7.
* Insertion sorts
**
Cycle sort: in-place with theoretically optimal number of writes
**
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. Howev ...
: determine where the current item belongs in the list of sorted ones, and insert it there
**
Library sort
A library is a collection of books, and possibly other materials and media, that is accessible for use by its members and members of allied institutions. Libraries provide physical (hard copies) or digital (soft copies) materials, and may be a p ...
**
Patience sorting
**
Shell sort: an attempt to improve insertion sort
**
Tree sort
A tree sort is a sort algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree ( in-order) so that the elements come out in sorted order. Its typical use is sorting elements online: after each inser ...
(binary tree sort): build binary tree, then traverse it to create sorted list
* Merge sorts
**
Merge sort
In computer science, merge sort (also commonly spelled as mergesort and as ) is an efficient, general-purpose, and comparison sort, comparison-based sorting algorithm. Most implementations of merge sort are Sorting algorithm#Stability, stable, wh ...
: sort the first and second half of the list separately, then merge the sorted lists
**
Slowsort
**
Strand sort
* Non-comparison sorts
**
Bead sort
**
Bucket sort
**
Burstsort
Burstsort and its variants are cache-efficient algorithms for sorting strings. They are variants of the traditional radix sort but faster for large data sets of common strings, first published in 2003, with some optimizing versions published i ...
: build a compact, cache efficient
burst trie and then traverse it to create sorted output
**
Counting sort
**
Pigeonhole sort
**
Postman sort: variant of Bucket sort which takes advantage of hierarchical structure
**
Radix sort: sorts strings letter by letter
* Selection sorts
**
Heapsort
In computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that ...
: 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 a O(''n''2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is note ...
: pick the smallest of the remaining elements, add it to the end of the sorted list
**
Smoothsort
In computer science, smoothsort is a comparison sort, comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of ...
* Other
**
Bitonic sorter
Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of O(n\log^2(n)) comparators and have ...
**
Pancake sorting
**
Spaghetti sort
**
Topological sort
* Unknown class
**
Samplesort
Samplesort is a sorting algorithm that is a divide and conquer algorithm often used in parallel processing systems. Conventional divide and conquer sorting algorithms partitions the array into sub-intervals or buckets. The buckets are then sorted i ...
Subsequences
*
Longest common subsequence problem
A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring: unlike substrings, subsequences are not required to occupy conse ...
: Find the longest subsequence common to all sequences in a set of sequences
*
Longest increasing subsequence problem: Find the longest increasing subsequence of a given sequence
*
Ruzzo–Tompa algorithm: 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 data structure, array A ...nof number ...
: finds the contiguous subarray with largest sum in an array of numbers
*
Longest common substring problem
Long may refer to:
Measurement
* Long, characteristic of something of great duration
* Long, characteristic of something of great length
* Longitude (abbreviation: long.), a geographic coordinate
* Longa (music), note value in early music mens ...
: find the longest string (or strings) that is a substring (or are substrings) of two or more strings
*
Matching wildcards
In computer science, an algorithm for matching wildcards (also known as globbing) is useful in comparing text strings that may contain wildcard character, wildcard syntax. Common uses of these algorithms include command-line interfaces, e.g. the Bo ...
**
Krauss matching wildcards algorithm In computer science, the Krauss wildcard-matching algorithm is a pattern matching algorithm. Based on the wildcard syntax in common use, e.g. in the Microsoft Windows command-line interface, the algorithm provides a non- recursive mechanism for mat ...
: an open-source non-recursive algorithm
**
Rich Salz'
wildmat
wildmat is a pattern matching library developed by Rich Salz. Based on the wildcard syntax already used in the Bourne shell, wildmat provides a uniform mechanism for matching patterns across applications with simpler syntax than that typicall ...
: 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 and view the source code, design documents, or content of the product. The open source model is a decentrali ...
recursive
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
algorithm
*
Substring search
**
Aho–Corasick string matching algorithm:
trie
In computer science, a trie (, ), also known as a digital tree or prefix tree, is a specialized search tree data structure used to store and retrieve strings from a dictionary or set. Unlike a binary search tree, nodes in a trie do not store t ...
based algorithm for finding all substring matches to any of a finite set of strings
**
Boyer–Moore–Horspool algorithm: Simplification of Boyer–Moore
**
Boyer–Moore string-search algorithm: amortized linear (
sublinear in most times) algorithm for substring search
**
Knuth–Morris–Pratt algorithm: 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
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an of ...
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 particu ...
s
Computational mathematics
Abstract algebra
*
Chien search: 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, determine whether a given permutati ...
: computing a base and
strong generating set (BSGS) of a
permutation group
In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to ...
*
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'' ...
: 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 K _1,\ldots,x_n/math> ove ...
*
Cantor–Zassenhaus algorithm: factor polynomials over finite fields
*
Faugère F4 algorithm: finds a Gröbner basis (also mentions the F5 algorithm)
*
Gosper's algorithm
In mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. ...
: 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 effectively ...
: 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
Multivariate is the quality of having multiple variables.
It may also refer to:
In mathematics
* Multivariable calculus
* Multivariate function
* Multivariate polynomial
* Multivariate interpolation
* Multivariate optimization
In computing
* ...
: for
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
s in several indeterminates
*
Pollard's kangaroo algorithm (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, bec ...
: an algorithm for dividing a polynomial by another polynomial of the same or lower degree
*
Risch algorithm: an algorithm for the calculus operation of indefinite integration (i.e. finding
antiderivatives
In calculus, an antiderivative, inverse derivative, primitive function, primitive integral or indefinite integral of a continuous function is a differentiable function whose derivative is equal to the original function . This can be stated s ...
)
Geometry
*
Closest pair problem: 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 an intersection of two or more objects in virtual space. More precisely, it deals with the questions of ''if'', ''when'' and ''where'' two or more objects intersect. Collision detect ...
algorithms: check for the collision or intersection of two given solids
*
Cone algorithm: identify surface points
*
Convex hull algorithms
Algorithms that construct convex hulls of various objects have a Convex hull#Applications, broad range of applications in mathematics and computer science.
In computational geometry, numerous algorithms are proposed for computing the convex hull o ...
: determining the
convex hull
In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...
of a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of points
**
Chan's algorithm
**
Gift wrapping algorithm
In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points.
Planar case
In the two-dimensional case the algorithm is also known as Jarvis march, after R. A. Jarvis, who publishe ...
or Jarvis march
**
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 ...
**
Kirkpatrick–Seidel algorithm
**
Quickhull
Quickhull is a method of computing the convex hull of a finite set of points in ''n''-dimensional space. It uses a divide and conquer approach similar to that of quicksort, from which its name derives. Its worst case time complexity for 2-dimensio ...
*
Euclidean distance transform: computes the distance between every point in a grid and a discrete collection of points.
*
Geometric hashing: 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 general ...
*
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: an algorithm for point location in triangulations
*
Laplacian smoothing: an algorithm to smooth a polygonal mesh
*
Line segment intersection: finding whether lines intersect, usually with a
sweep line algorithm
In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm that uses a conceptual ''sweep line'' or ''sweep surface'' to solve various problems in Euclidean space. It is one of the critical techniques in ...
**
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
*
Nesting algorithm: make the most efficient use of material or space
*
Point in polygon
In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It is a special case of point location problems and finds applications in areas that deal ...
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
In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter (computational geometry), diameter of a set of points.
The method ...
: determine all
antipodal
Antipode or Antipodes may refer to:
Mathematics
* Antipodal point, the diametrically opposite point on a circle or ''n''-sphere, also known as an antipode
* Antipode, the convolution inverse of the identity on a Hopf algebra
Geography
* Antipodes ...
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 ...
or
convex hull
In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...
.
*
Shoelace algorithm: 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 m ...
**
Delaunay triangulation
In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...
***
Chew's second algorithm: create quality
constrained Delaunay triangulations
***
Ruppert's algorithm (also known as Delaunay refinement): create quality Delaunay triangulations
**
Marching triangles: reconstruct two-dimensional surface geometry from an unstructured
point cloud
A point cloud is a discrete set of data Point (geometry), points in space. The points may represent a 3D shape or object. Each point Position (geometry), position has its set of Cartesian coordinates (X, Y, Z). Points may contain data other than ...
**
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
**
Quasitriangulation
**
Voronoi diagram
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane (calle ...
s, geometric
dual of
Delaunay triangulation
In computational geometry, a Delaunay triangulation or Delone triangulation of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its gen ...
***
Bowyer–Watson algorithm
In computational geometry, the Bowyer–Watson algorithm is a method for computing the Delaunay triangulation of a finite set of points in any number of dimensions. The algorithm can be also used to obtain a Voronoi diagram of the points, which i ...
: create voronoi diagram in any number of dimensions
***
Fortune's Algorithm: create voronoi diagram
Number theoretic algorithms
*
Binary GCD algorithm: Efficient way of calculating GCD.
*
Booth's multiplication algorithm
Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed base 2, binary numbers in two's complement, two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crys ...
*
Chakravala method
The ''chakravala'' method () 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 – Students' Britannica India: Bhask ...
: 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 Square number, nonsquare integer, and integer solutions are sought for ''x'' and ''y''. In Cartesian ...
*
Discrete logarithm
In mathematics, for given real numbers a and b, the logarithm \log_b(a) is a number x such that b^x=a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm \log_b(a) is an integer k such that b^k=a ...
:
**
Baby-step giant-step
**
Index calculus algorithm In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms.
Dedicated to the discrete logarithm in (\mathbb/q\mathbb)^* where q is a prime, index calculus leads to a family of algori ...
**
Pohlig–Hellman algorithm
**
Pollard's rho algorithm for logarithms
*
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 a ...
: computes the
greatest common divisor
In mathematics, the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers , , the greatest co ...
*
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 id ...
: also solves the equation ''ax'' + ''by'' = ''c''
*
Integer factorization
In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
: 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 ways ...
factors
**
Congruence of squares
**
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
:
\begin
& ...
**
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 algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong ...
**
Special number field sieve
Special or specials may refer to:
Policing
* Specials, Ulster Special Constabulary, the Northern Ireland police force
* Specials, Special Constable, an auxiliary, volunteer, or temporary; police worker or police officer
* Special police forces
...
**
Trial division
*
Lenstra–Lenstra–Lovász algorithm (also known as LLL algorithm): find a short, nearly orthogonal
lattice basis in polynomial time
*
Modular square root: computing square roots modulo a prime number
**
Berlekamp's root finding algorithm
**
Cipolla's algorithm
**
Tonelli–Shanks algorithm
*
Multiplication algorithm
A multiplication algorithm is an algorithm (or method) to multiplication, multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Numerous algorithms are known and there has been much resea ...
s: fast multiplication of two numbers
**
Karatsuba algorithm
The Karatsuba algorithm is a fast multiplication algorithm for integers. It was discovered by Anatoly Karatsuba in 1960 and published in 1962.
Knuth D.E. (1969) '' The Art of Computer Programming. v.2.'' Addison-Wesley Publ.Co., 724 pp ...
**
Schönhage–Strassen algorithm
**
Toom–Cook multiplication
Toom–Cook, sometimes known as Toom-3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm for large integers.
Given two large in ...
*
Odlyzko–Schönhage algorithm: calculates nontrivial zeroes of the
Riemann zeta function
The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for and its analytic c ...
*
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 wheth ...
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 ways ...
**
AKS primality test
The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientist ...
**
Baillie–PSW primality test
The Baillie–PSW primality test is a probabilistic or possibly deterministic 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, ...
**
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 number, composite (i.e., not prime) the multiples of each prime, starting with ...
**
Sieve of Sundaram
Numerical algorithms
Differential equation solving
*
Backward Euler method
In numerical analysis and scientific computing, the backward Euler method (or implicit Euler method) is one of the most basic numerical methods for ordinary differential equations, numerical methods for the solution of ordinary differential equatio ...
*
Euler method
In mathematics and computational science, the Euler method (also called the forward Euler method) is a first-order numerical analysis, numerical procedure for solving ordinary differential equations (ODEs) with a given Initial value problem, in ...
*
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
*
Multigrid methods (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 involves a multivariable function and one or more of its partial derivatives.
The function is often thought of as an "unknown" that solves the equation, similar to ho ...
:
**
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 Big O notation, second-order method in time. It is Explicit and im ...
for diffusion equations
**
Finite difference method
In numerical analysis, finite-difference methods (FDM) are a class of numerical techniques for solving differential equations by approximating Derivative, derivatives with Finite difference approximation, finite differences. Both the spatial doma ...
**
Lax–Wendroff for wave equations
*
Runge–Kutta methods
In numerical analysis, the Runge–Kutta methods ( ) are a family of Explicit and implicit methods, implicit and explicit iterative methods, List of Runge–Kutta methods, which include the Euler method, used in temporal discretization for the a ...
**
Euler integration
*
Trapezoidal rule (differential equations)
In numerical analysis and scientific computing, the trapezoidal rule is a numerical method to solve ordinary differential equations derived from the trapezoidal rule for computing integrals. The trapezoidal rule is an implicit second-order method ...
*
Verlet integration
Verlet integration () is a numerical method used to integrate Newton's equations of motion. It is frequently used to calculate trajectories of particles in molecular dynamics simulations and computer graphics. The algorithm was first used in 17 ...
(): integrate Newton's equations of motion
Elementary and special functions
*
Computation of π:
**
Bailey–Borwein–Plouffe formula: (BBP formula) a spigot algorithm for the computation of the nth binary digit of π
**
Borwein's algorithm: an algorithm to calculate the value of 1/π
**
Chudnovsky algorithm
The Chudnovsky algorithm is a fast method for calculating the digits of , based on Ramanujan's formulae. Published by the Chudnovsky brothers in 1988, it was used to calculate to a billion decimal places.
It was used in the world record calcu ...
: a fast method for calculating the digits of π
**
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
*
Division algorithm
A division algorithm is an algorithm which, given two integers ''N'' and ''D'' (respectively the numerator and the denominator), computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others ar ...
s: for computing quotient and/or remainder of two numbers
**
Goldschmidt division
**
Long division
In arithmetic, long division is a standard division algorithm suitable for dividing multi-digit Hindu-Arabic numerals (positional notation) that is simple enough to perform by hand. It breaks down a division problem into a series of easier step ...
**
Newton–Raphson division
A division algorithm is an algorithm which, given two integers ''N'' and ''D'' (respectively the numerator and the denominator), computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others ar ...
: uses
Newton's method
In numerical analysis, the Newton–Raphson method, also known simply as Newton's 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 ...
to find the
reciprocal of D, and multiply that reciprocal by N to find the final quotient Q.
**
Non-restoring division
**
Restoring division
**
SRT division
* 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
* Hyperbolic and Trigonometric Functions:
**
BKM algorithm: computes
elementary functions using a table of logarithms
**
CORDIC
CORDIC, short for coordinate rotation digital computer, is a simple and efficient algorithm to calculate trigonometric functions, hyperbolic functions, square roots, multiplications, divisions, and exponentials and logarithms
In ma ...
: computes hyperbolic and trigonometric functions using a table of arctangents
*
Montgomery reduction: an algorithm that allows
modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to mo ...
to be performed efficiently when the modulus is large
*
Multiplication algorithm
A multiplication algorithm is an algorithm (or method) to multiplication, multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Numerous algorithms are known and there has been much resea ...
s: fast multiplication of two numbers
**
Booth's multiplication algorithm
Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed base 2, binary numbers in two's complement, two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crys ...
: 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
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
**
Karatsuba algorithm
The Karatsuba algorithm is a fast multiplication algorithm for integers. It was discovered by Anatoly Karatsuba in 1960 and published in 1962.
Knuth D.E. (1969) '' The Art of Computer Programming. v.2.'' Addison-Wesley Publ.Co., 724 pp ...
: an efficient procedure for multiplying large numbers
**
Schönhage–Strassen algorithm: an asymptotically fast multiplication algorithm for large integers
**
Toom–Cook multiplication
Toom–Cook, sometimes known as Toom-3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm for large integers.
Given two large in ...
: (Toom3) a multiplication algorithm for large integers
*
Multiplicative inverse Algorithms: for computing a number's multiplicative inverse (reciprocal).
**
Newton's method
In numerical analysis, the Newton–Raphson method, also known simply as Newton's 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 ...
*
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 number whose value is fixed by an unambiguous definition, often referred to by a special symbol (e.g., an Letter (alphabet), alphabet letter), or by mathematicians' names to facilitate using it across multiple mathem ...
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
* Summation:
**
Binary splitting: a
divide and conquer 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.
*
Level set method (LSM): a numerical technique for tracking interfaces and shapes
Interpolation and extrapolation
*
Birkhoff interpolation
In mathematics, Birkhoff interpolation is an extension of polynomial interpolation. It refers to the problem of finding a polynomial P(x) of degree d such that ''only certain'' derivatives have specified values at specified points:
: P^(x_i) = y_ ...
: an extension of polynomial interpolation
*
Cubic interpolation
In numerical analysis, a cubic Hermite spline or cubic Hermite interpolator is a spline where each piece is a third-degree polynomial specified in Hermite form, that is, by its values and first derivatives at the end points of the correspondin ...
*
Hermite interpolation
In numerical analysis, Hermite interpolation, named after Charles Hermite, is a method of polynomial interpolation, which generalizes Lagrange interpolation. Lagrange interpolation allows computing a polynomial of degree less than that takes th ...
*
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'' ...
: 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'' ...
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: a variant of cubic interpolation that preserves monotonicity of the data set being interpolated.
*
Multivariate interpolation
In numerical analysis, multivariate interpolation or multidimensional interpolation is interpolation on ''multivariate functions'', having more than one variable or defined over a multi-dimensional domain. A common special case is bivariate inter ...
**
Bicubic interpolation
In mathematics, bicubic interpolation is an extension of cubic spline interpolation (a method of applying cubic interpolation to a data set) for interpolating data points on a two-dimensional regular grid. The interpolated surface (meaning the k ...
: a generalization of
cubic interpolation
In numerical analysis, a cubic Hermite spline or cubic Hermite interpolator is a spline where each piece is a third-degree polynomial specified in Hermite form, that is, by its values and first derivatives at the end points of the correspondin ...
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
Lanczos filtering and Lanczos resampling are two applications of a certain mathematical formula. It can be used as a low-pass filter or used to smoothly interpolate the value of a digital signal between its samples. In the latter case, it maps ...
("Lanzosh"): a multivariate interpolation method used to compute new values for any digitally sampled data
**
Nearest-neighbor interpolation
Nearest-neighbor interpolation (also known as proximal interpolation or, in some contexts, point sampling) is a simple method of multivariate interpolation in one or more dimensions.
Interpolation is the problem of approximating the value of a ...
**
Tricubic interpolation
In the mathematical subfield numerical analysis, tricubic interpolation is a method for obtaining values at arbitrary points in Three-dimensional space, 3D space of a function defined on a regular grid. The approach involves approximating the fun ...
: a generalization of
cubic interpolation
In numerical analysis, a cubic Hermite spline or cubic Hermite interpolator is a spline where each piece is a third-degree polynomial specified in Hermite form, that is, by its values and first derivatives at the end points of the correspondin ...
to three dimensions
*
Pareto interpolation
Pareto interpolation is a method of estimator, estimating the median and other properties of a population that follows a Pareto distribution. It is used in economics when analysing the distribution of incomes in a population, when one must base es ...
: 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, actuarial scien ...
.
*
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 in the dataset.
Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with no ...
**
Neville's algorithm
*
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 numerical analysis, a B-spline (short for basis spline) is a type of Spline (mathematics), spline function designed to have minimal Support (mathematics), support (overlap) for a given Degree of a polynomial, degree, smoothness, and set of bre ...
s
**
De Casteljau's algorithm:
Bézier curve
A Bézier curve ( , ) is a parametric equation, parametric curve used in computer graphics and related fields. A set of discrete "control points" defines a smooth, continuous curve by means of a formula. Usually the curve is intended to approxima ...
s
*
Trigonometric interpolation
Linear algebra
*
Eigenvalue algorithm
In numerical analysis, one of the most important problems is designing efficient and Numerical stability, stable algorithms for finding the eigenvalues of a Matrix (mathematics), matrix. These eigenvalue algorithms may also find eigenvectors.
Eig ...
s
**
Arnoldi iteration
In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of an iterative method. Arnoldi finds an approximation to the eigenvalues and eigenvectors of general (possibly non- Hermitian) matrices by c ...
**
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 m ...
**
Jacobi method
**
Lanczos iteration
The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that is an adaptation of power methods to find the m "most useful" (tending towards extreme highest/lowest) eigenvalues and eigenvectors
In linear algebra, an eige ...
**
Power iteration
In mathematics, power iteration (also known as the power method) is an eigenvalue algorithm: given a diagonalizable matrix A, the algorithm will produce a number \lambda, which is the greatest (in absolute value) eigenvalue of A, and a nonzero vec ...
**
QR algorithm
**
Rayleigh quotient iteration
*
Gram–Schmidt process
In mathematics, particularly linear algebra and numerical analysis, the Gram–Schmidt process or Gram-Schmidt algorithm is a way of finding a set of two or more vectors that are perpendicular to each other.
By technical definition, it is a metho ...
: orthogonalizes a set of vectors
* Krylov methods (for large sparse matrix problems; third most-important numerical method class of the 20th century as ranked by SISC; after fast-fourier and fast-multipole)
*
Matrix multiplication algorithm
Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in m ...
s
**
Cannon's algorithm: a
distributed algorithm A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientifi ...
for
matrix multiplication
In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix (mathematics), matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the n ...
especially suitable for computers laid out in an N × N mesh
**
Coppersmith–Winograd algorithm: square
matrix multiplication
In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix (mathematics), matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the n ...
**
Freivalds' algorithm Freivalds' algorithm (named after Rūsiņš Mārtiņš Freivalds) is a probabilistic randomized algorithm used to verify matrix multiplication. Given three ''n'' × ''n'' matrices A, B, and C, a general problem is to verify whether A ...
: a randomized algorithm used to verify matrix multiplication
**
Strassen algorithm
In linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm for matrix multiplication. It is faster than the standard matrix multiplication algorithm for large matrices, with a better asymptotic complexity, although t ...
: faster
matrix multiplication
In mathematics, specifically in linear algebra, matrix multiplication is a binary operation that produces a matrix (mathematics), matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the n ...
* Solving
systems of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of two or more linear equations involving the same variables.
For example,
: \begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three equations in ...
**
Biconjugate gradient method
In mathematics, more specifically in numerical linear algebra, the biconjugate gradient method is an algorithm to solve systems of linear equations
:A x= b.\,
Unlike the conjugate gradient method, this algorithm does not require the matrix A to ...
: solves systems of linear equations
**
Conjugate gradient
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-semidefinite. The conjugate gradient method is often implemented as an it ...
: an algorithm for the numerical solution of particular systems of linear equations
**
Gauss–Jordan elimination: solves systems of linear equations
**
Gauss–Seidel method
In numerical linear algebra, the Gauss–Seidel method, also known as the Liebmann method or the method of successive displacement, is an iterative method used to solve a system of linear equations. It is named after the German mathematicians Ca ...
: solves systems of linear equations iteratively
**
Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can a ...
**
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
In numerical linear algebra, the method of successive over-relaxation (SOR) is a variant of the Gauss–Seidel method for solving a linear system of equations, resulting in faster convergence. A similar method can be used for any slowly convergi ...
(SOR): method used to speed up convergence of the
Gauss–Seidel method
In numerical linear algebra, the Gauss–Seidel method, also known as the Liebmann method or the method of successive displacement, is an iterative method used to solve a system of linear equations. It is named after the German mathematicians Ca ...
**
Tridiagonal matrix algorithm
In numerical linear algebra, the tridiagonal matrix algorithm, also known as the Thomas algorithm (named after Llewellyn Thomas), is a simplified form of Gaussian elimination that can be used to solve Tridiagonal matrix, tridiagonal systems of equa ...
(Thomas algorithm): solves systems of tridiagonal equations
*
Sparse matrix
In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse ...
algorithms
**
Cuthill–McKee algorithm
In numerical linear algebra, the Cuthill–McKee algorithm (CM), named after Elizabeth Cuthill and James McKee,E. Cuthill and J. McKeethe bandwidth of sparse symmetric matrices''In Proc. 24th Nat. Conf. Association for Computing Machinery, ACM, ...
: reduce the
bandwidth
Bandwidth commonly refers to:
* Bandwidth (signal processing) or ''analog bandwidth'', ''frequency bandwidth'', or ''radio bandwidth'', a measure of the width of a frequency range
* Bandwidth (computing), the rate of data transfer, bit rate or thr ...
of a
symmetric sparse matrix
**
Minimum degree algorithm: permute the rows and columns of a
symmetric sparse matrix before applying the
Cholesky decomposition
In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced ) is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for eff ...
**
Symbolic Cholesky decomposition
In the mathematical subfield of numerical analysis the symbolic Cholesky decomposition is an algorithm used to determine the non-zero pattern for the L factors of a symmetric sparse matrix when applying the Cholesky decomposition or variants.
Al ...
: Efficient way of storing
sparse matrix
In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse ...
Monte Carlo
*
Gibbs sampling
In statistics, Gibbs sampling or a Gibbs sampler is a Markov chain Monte Carlo (MCMC) algorithm for sampling from a specified multivariate distribution, multivariate probability distribution when direct sampling from the joint distribution is dif ...
: 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
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified Hamiltonian ...
weighted
Markov chain Monte Carlo
In statistics, Markov chain Monte Carlo (MCMC) is a class of algorithms used to draw samples from a probability distribution. Given a probability distribution, one can construct a Markov chain whose elements' distribution approximates it – that ...
, from a probability distribution which is difficult to sample directly.
*
Metropolis–Hastings algorithm
In statistics and statistical physics, the Metropolis–Hastings algorithm is a Markov chain Monte Carlo (MCMC) method for obtaining a sequence of random samples from a probability distribution from which direct sampling is difficult. New sample ...
: used to generate a sequence of samples from the
probability distribution
In probability theory and statistics, a probability distribution is a Function (mathematics), function that gives the probabilities of occurrence of possible events for an Experiment (probability theory), experiment. It is a mathematical descri ...
of one or more variables
*
Wang and Landau algorithm: an extension of
Metropolis–Hastings algorithm
In statistics and statistical physics, the Metropolis–Hastings algorithm is a Markov chain Monte Carlo (MCMC) method for obtaining a sequence of random samples from a probability distribution from which direct sampling is difficult. New sample ...
sampling
Numerical integration
*
MISER algorithm: Monte Carlo simulation,
numerical integration
In analysis, numerical integration comprises a broad family of algorithms for calculating the numerical value of a definite integral.
The term numerical quadrature (often abbreviated to quadrature) is more or less a synonym for "numerical integr ...
Root finding
*
Bisection method
In mathematics, the bisection method is a root-finding method that applies to any continuous function for which one knows two values with opposite signs. The method consists of repeatedly bisecting the interval defined by these values and t ...
*
False position method
In mathematics, the ''regula falsi'', method of false position, or false position method is a very old method for solving an equation with one unknown; this method, in modified form, is still in use. In simple terms, the method is the trial and er ...
: and Illinois method: 2-point, bracketing
*
Halley's method: uses first and second derivatives
*
ITP method: minmax optimal and superlinear convergence simultaneously
*
Muller's method: 3-point, quadratic interpolation
*
Newton's method
In numerical analysis, the Newton–Raphson method, also known simply as Newton's 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 ...
: finds zeros of functions with
calculus
Calculus is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithmetic operations.
Originally called infinitesimal calculus or "the ...
*
Ridder's method: 3-point, exponential scaling
*
Secant method: 2-point, 1-sided
Optimization algorithms
Hybrid Algorithms
*
Alpha–beta pruning
Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the Minimax#Minimax algorithm with alternate moves, minimax algorithm in its game tree, search tree. It is an adversarial search algorith ...
: search to reduce number of nodes in minimax algorithm
*
A hybrid BFGS-Like method (see more https://doi.org/10.1016/j.cam.2024.115857)
*
Branch and bound
Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution.
It is an algorithm ...
*
Bruss algorithm: see
odds algorithm
In decision theory, the odds algorithm (or Bruss algorithm) is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of optimal stopping problems. Their solution follows from the ''odds strategy' ...
*
Chain matrix multiplication
*
Combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...
: 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
The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:
:The problem instance has a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any t ...
in polynomial time
*
Conjugate gradient method
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-semidefinite. The conjugate gradient method is often implemented as an it ...
s (see more https://doi.org/10.1016/j.jksus.2022.101923)
*
Constraint satisfaction In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through
a set of constraints that impose conditions that the variables must satisfy. A solution is therefore an assignment of value ...
**
AC-3 algorithm general algorithms for the constraint satisfaction
**
Chaff algorithm
Chaff is an algorithm for solving instances of the Boolean satisfiability problem in programming. It was designed by researchers at Princeton University. The algorithm is an instance of the DPLL algorithm with a number of enhancements for efficien ...
: an algorithm for solving instances of the
Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an Interpretation (logic), interpretation that Satisf ...
**
Davis–Putnam algorithm: check the validity of a first-order logic formula
**
Difference map algorithm general algorithms for the constraint satisfaction
**
Davis–Putnam–Logemann–Loveland algorithm
In logic and computer science, the Davis–Putnam–Logemann–Loveland (DPLL) algorithm is a complete, backtracking-based search algorithm for deciding the satisfiability of propositional logic formulae in conjunctive normal form, i.e. for s ...
(DPLL): an algorithm for deciding the satisfiability of propositional logic formula in
conjunctive normal form
In Boolean algebra, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs.
In au ...
, i.e. for solving the
CNF-SAT problem
**
Exact cover
In the mathematical field of combinatorics, given a collection \mathcal of subsets of a set X, an exact cover is a subcollection \mathcal^ of \mathcal such that each element in X is contained in ''exactly one'' subset in \mathcal^.
One says that e ...
problem
**
Min conflicts algorithm general algorithms for the constraint satisfaction
***
Algorithm X
Algorithm X is an algorithm for solving the exact cover problem. It is a straightforward Recursion (computer science), recursive, Nondeterministic algorithm, nondeterministic, depth-first, backtracking algorithm used by Donald Knuth to demonstrate ...
: a
nondeterministic algorithm
In computer science and computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.
Different models of computation ...
***
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
Importance sampling is a Monte Carlo method for evaluating properties of a particular distribution, while only having samples generated from a different distribution than the distribution of interest. Its introduction in statistics is generally at ...
*
Differential evolution
*
Dynamic Programming: problems exhibiting the properties of
overlapping subproblems and
optimal substructure
In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.{{cite bo ...
*
Ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for convex optimization, minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every ste ...
: is an algorithm for solving convex optimization problems
*
Evolutionary computation
Evolutionary computation from computer science is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms ...
: optimization inspired by biological mechanisms of evolution
**
Evolution strategy
Evolution strategy (ES) from computer science is a subclass of evolutionary algorithms, which serves as an optimization (mathematics), optimization technique. It uses the major genetic operators mutation (evolutionary algorithm), mutation, recomb ...
**
Gene expression programming
Gene expression programming (GEP) in computer programming is an evolutionary algorithm that creates computer programs or models. These computer programs are complex tree structures that learn and adapt by changing their sizes, shapes, and compos ...
**
Genetic algorithms
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to g ...
***
Fitness proportionate selection
Fitness proportionate selection, also known as roulette wheel selection or spinning wheel selection, is a selection technique used in evolutionary algorithms for selecting potentially useful solutions for recombination.
Method
In fitness prop ...
– also known as roulette-wheel selection
***
Stochastic universal sampling
Stochastic universal sampling (SUS) is a selection technique used in evolutionary algorithm
Evolutionary algorithms (EA) reproduce essential elements of the biological evolution in a computer algorithm in order to solve "difficult" problems, at ...
***
Tournament selection
Tournament selection is a method of selecting an individual from a population of individuals in a evolutionary algorithm. Tournament selection involves running several "tournaments" among a few individuals (or "chromosomes") chosen at random from t ...
***
Truncation selection
Truncation selection is a selection method in selective breeding and in evolutionary algorithms from computer science, which selects a certain share of fittest individuals from a population for reproduction in the next generation.
Animal and pl ...
**
Memetic algorithm
In computer science and operations research, a memetic algorithm (MA) is an extension of an evolutionary algorithm (EA) that aims to accelerate the evolutionary search for the optimum. An EA is a metaheuristic that reproduces the basic principl ...
**
Swarm intelligence
Swarm intelligence (SI) is the collective behavior of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence. The expression was introduced by Gerardo Beni and Jing Wang in 198 ...
***
Ant colony optimization
In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems that can be reduced to finding good paths through graphs. Artificial ants represent multi ...
***
Bees algorithm: a search algorithm which mimics the food foraging behavior of swarms of honey bees
***
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
Gradient descent is a method for unconstrained mathematical optimization. It is a first-order iterative algorithm for minimizing a differentiable multivariate function.
The idea is to take repeated steps in the opposite direction of the gradi ...
*
Grid Search
*
Harmony search (HS): a
metaheuristic
In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an op ...
algorithm mimicking the improvisation process of musicians
*
A hybrid HS-LS conjugate gradient algorithm (see https://doi.org/10.1016/j.cam.2023.115304)
*
Interior point method
Interior-point methods (also referred to as barrier methods or IPMs) are algorithms for solving Linear programming, linear and nonlinear programming, non-linear convex optimization problems. IPMs combine two advantages of previously-known algorit ...
*
Line search
In optimization, line search is a basic iterative approach to find a local minimum \mathbf^* of an objective function f:\mathbb R^n\to\mathbb R. It first finds a descent direction along which the objective function f will be reduced, and then co ...
*
Linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
**
Benson's algorithm: an algorithm for solving linear
vector optimization
Vector optimization is a subarea of mathematical optimization where Optimization problem, optimization problems with a vector-valued objective functions are optimized with respect to a given partial ordering and subject to certain constraints. A m ...
problems
**
Dantzig–Wolfe decomposition
Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Philip Wolfe and initially published in 1960. Many texts on linear programming have s ...
: an algorithm for solving linear programming problems with special structure
**
Delayed column generation
Column generation or delayed column generation is an efficient algorithm for solving large linear programs.
The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by so ...
**
Integer linear programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...
: solve linear programming problems where some or all the unknowns are restricted to integer values
***
Branch and cut
Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branc ...
***
Cutting-plane method
In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed ''cuts''. Such procedures are commonly used ...
**
Karmarkar's algorithm: The first reasonably efficient algorithm that solves the
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
problem in
polynomial time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
.
**
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are ...
: an algorithm for solving
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
problems
*
Local search: a metaheuristic for solving computationally hard optimization problems
**
Random-restart hill climbing
**
Tabu search Tabu search (TS) is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986
and formalized in 1989.
Local (neighborhood) searches take a potential solution to a ...
*
Minimax
Minimax (sometimes Minmax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy for ''minimizing'' the possible loss function, loss for a Worst-case scenari ...
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
In mathematics, a metric space is a Set (mathematics), set together with a notion of ''distance'' between its Element (mathematics), elements, usually called point (geometry), points. The distance is measured by a function (mathematics), functi ...
**
Best Bin First: find an approximate solution to the
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: ...
problem in very-high-dimensional spaces
*
Newton's method in optimization
In calculus, Newton's method (also called Newton–Raphson) is an iterative method for finding the roots of a differentiable function f, which are solutions to the equation f(x)=0. However, to optimize a twice-differentiable f, our goal is to f ...
*
Nonlinear optimization
**
BFGS method: a
nonlinear optimization algorithm
**
Gauss–Newton algorithm: an algorithm for solving nonlinear
least squares
The method of least squares is a mathematical optimization technique that aims to determine the best fit function by minimizing the sum of the squares of the differences between the observed values and the predicted values of the model. The me ...
problems
**
Levenberg–Marquardt algorithm
In mathematics and computing, the Levenberg–Marquardt algorithm (LMA or just LM), also known as the damped least-squares (DLS) method, is used to solve non-linear least squares problems. These minimization problems arise especially in least s ...
: an algorithm for solving nonlinear
least squares
The method of least squares is a mathematical optimization technique that aims to determine the best fit function by minimizing the sum of the squares of the differences between the observed values and the predicted values of the model. The me ...
problems
**
Nelder–Mead method
The Nelder–Mead method (also downhill simplex method, amoeba method, or polytope method) is a numerical method used to find the minimum or maximum of an objective function in a multidimensional space. It is a direct search method (based on ...
(downhill simplex method): a
nonlinear optimization algorithm
*
Odds algorithm
In decision theory, the odds algorithm (or Bruss algorithm) is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of optimal stopping problems. Their solution follows from the ''odds strategy' ...
(Bruss algorithm): Finds the optimal strategy to predict a last specific event in a random sequence event
*
Random Search
Random search (RS) is a family of numerical optimization methods that do not require the gradient of the optimization problem, and RS can hence be used on functions that are not continuous or differentiable. Such optimization methods are also kno ...
*
Simulated annealing
Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. ...
*
Stochastic tunneling
*
Subset sum algorithm
Computational science
Astronomy
*
Doomsday algorithm: day of the week
* various
Easter algorithms are used to calculate the day of Easter
*
Zeller's congruence is an algorithm to calculate the day of the week for any Julian or Gregorian calendar date
Bioinformatics
*
Basic Local Alignment Search Tool also known as BLAST: an algorithm for comparing primary biological sequence information
*
Bloom Filter
In computing, a Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives ar ...
: probabilistic data structure used to test for the existence of an element within a set. Primarily used in bioinformatics to test for the existence of a
k-mer
In bioinformatics, ''k''-mers are substrings of length k contained within a biological sequence. Primarily used within the context of computational genomics and sequence analysis, in which ''k''-mers are composed of nucleotides (''i.e''. A, T, ...
in a sequence or sequences.
*
Kabsch algorithm: calculate the optimal alignment of two sets of points in order to compute the
root mean squared deviation between two protein structures.
*
Maximum parsimony (phylogenetics)
In phylogenetics and computational phylogenetics, maximum parsimony is an optimality criterion under which the phylogenetic tree that minimizes the total number of character-state changes (or minimizes the cost of differentially weighted charact ...
: an algorithm for finding the simplest phylogenetic tree to explain a given character matrix.
*
Sorting by signed reversals: an algorithm for understanding genomic evolution.
*
UPGMA
UPGMA (unweighted pair group method with arithmetic mean) is a simple agglomerative (bottom-up) hierarchical clustering method. It also has a weighted variant, WPGMA, and they are generally attributed to Sokal and Michener.
Note that the unwei ...
: a distance-based phylogenetic tree construction algorithm.
*
Velvet
Velvet is a type of woven fabric with a dense, even pile (textile), pile that gives it a distinctive soft feel. Historically, velvet was typically made from silk. Modern velvet can be made from silk, linen, cotton, wool, synthetic fibers, silk ...
: a set of algorithms manipulating
de Bruijn graph
In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple ...
s for genomic
sequence assembly
Geoscience
*
Geohash
Geohash is a public domain geocode system invented in 2008 by Gustavo Niemeyer
*
*
* which encodes a geographic location into a short string of letters and digits. Similar ideas were introduced by G.M. Morton in 1966. It is a hierarchical spat ...
: a public domain algorithm that encodes a decimal latitude/longitude pair as a hash string
*
Vincenty's formulae
Vincenty's formulae are two related iterative methods used in geodesy to calculate the distance between two points on the surface of a spheroid, developed by Thaddeus Vincenty (1975a). They are based on the assumption that the figure of the Eart ...
: a fast algorithm to calculate the distance between two latitude/longitude points on an ellipsoid
Linguistics
*
Lesk algorithm: word sense disambiguation
*
Stemming algorithm
In linguistic morphology and information retrieval, stemming is the process of reducing inflected (or sometimes derived) words to their word stem, base or root form—generally a written word form. The stem need not be identical to the morpholo ...
: 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
Pulmonary embolism (PE) is a blockage of an pulmonary artery, artery in the lungs by a substance that has moved from elsewhere in the body through the bloodstream (embolism). Symptoms of a PE may include dyspnea, shortness of breath, chest pain ...
diagnostic algorithms
*
Texas Medication Algorithm Project
Physics
*
Constraint algorithm
In computational chemistry, a constraint algorithm is a method for satisfying the Newtonian motion of a rigid body which consists of mass points. A restraint algorithm is used to ensure that the distance between mass points is maintained. The gen ...
: a class of algorithms for satisfying constraints for bodies that obey Newton's equations of motion
*
Demon algorithm: a
Monte Carlo method
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be ...
for efficiently sampling members of a
microcanonical ensemble
In statistical mechanics, the microcanonical ensemble is a statistical ensemble that represents the possible states of a mechanical system whose total energy is exactly specified. The system is assumed to be isolated in the sense that it canno ...
with a given energy
*
Featherstone's algorithm
Featherstone's algorithm is a technique used for computing the effects of forces applied to a structure of joints and links (an "open kinematic chain") such as a skeleton used in ragdoll physics.
The Featherstone's algorithm uses a reduced coordi ...
: computes the effects of forces applied to a structure of joints and links
*
Glauber dynamics: a method for simulating the Ising Model on a computer
*
Ground state
The ground state of a quantum-mechanical system is its stationary state of lowest energy; the energy of the ground state is known as the zero-point energy of the system. An excited state is any state with energy greater than the ground state ...
approximation
**
Variational method
***
Ritz method
*
''n''-body problems
**
Barnes–Hut simulation
The Barnes–Hut simulation (named after Joshua Barnes and Piet Hut) is an approximation algorithm for performing an N-body simulation. It is notable for having Big O notation, order O(''n'' log ''n'') compared to a direct-sum algorithm ...
: 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 history to a count of elementary stress-reversals for use in
fatigue
Fatigue is a state of tiredness (which is not sleepiness), exhaustion or loss of energy. It is a signs and symptoms, symptom of any of various diseases; it is not a disease in itself.
Fatigue (in the medical sense) is sometimes associated wit ...
analysis
*
Sweep and prune: a broad phase algorithm used during
collision detection
Collision detection is the computational problem of detecting an intersection of two or more objects in virtual space. More precisely, it deals with the questions of ''if'', ''when'' and ''where'' two or more objects intersect. Collision detect ...
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 simulation
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be det ...
s
Statistics
*
Algorithms for calculating variance
Algorithms for calculating variance play a major role in computational statistics. A key difficulty in the design of good algorithms for this problem is that formulas for the variance may involve sums of squares, which can lead to numerical insta ...
: avoiding instability and numerical overflow
*
Approximate counting algorithm: allows counting large number of events in a small register
*
Bayesian statistics
Bayesian statistics ( or ) is a theory in the field of statistics based on the Bayesian interpretation of probability, where probability expresses a ''degree of belief'' in an event. The degree of belief may be based on prior knowledge about ...
**
Nested sampling algorithm: a computational approach to the problem of comparing models in Bayesian statistics
*
Clustering algorithms
**
Average-linkage clustering: a simple agglomerative clustering algorithm
**
Canopy clustering algorithm: an unsupervised pre-clustering algorithm related to the K-means algorithm
**
Chinese whispers
Telephone (American English and Canadian English), or Chinese whispers (some Commonwealth English), is an internationally popular children's game in which messages are whispered from person to person and then the original and final messages are ...
**
Complete-linkage clustering
Complete-linkage clustering is one of several methods of agglomerative hierarchical clustering. At the beginning of the process, each element is in a cluster of its own. The clusters are then sequentially combined into larger clusters until all ...
: 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
***
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
***
Fuzzy c-means
**
k-means clustering
''k''-means clustering is a method of vector quantization, originally from signal processing, that aims to partition of a set, partition ''n'' observations into ''k'' clusters in which each observation belongs to the cluster (statistics), cluste ...
: cluster objects based on attributes into partitions
**
k-means++: a variation of this, using modified random seeds
**
k-medoids
-medoids is a classical partitioning technique of clustering that splits the data set of objects into clusters, where the number of clusters assumed known ''a priori'' (which implies that the programmer must specify k before the execution of a - ...
: similar to k-means, but chooses datapoints or
medoids as centers
**
KHOPCA clustering algorithm: a local clustering algorithm, which produces hierarchical multi-hop clusters in static and mobile environments.
**
Linde–Buzo–Gray algorithm: a vector quantization algorithm to derive a good codebook
**
Lloyd's algorithm
In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of ...
(Voronoi iteration or relaxation): group data points into a given number of categories, a popular algorithm for
k-means clustering
''k''-means clustering is a method of vector quantization, originally from signal processing, that aims to partition of a set, partition ''n'' observations into ''k'' clusters in which each observation belongs to the cluster (statistics), cluste ...
**
OPTICS
Optics is the branch of physics that studies the behaviour and properties of light, including its interactions with matter and the construction of optical instruments, instruments that use or Photodetector, detect it. Optics usually describes t ...
: a density based clustering algorithm with a visual evaluation method
**
Single-linkage clustering
In statistics, single-linkage clustering is one of several methods of hierarchical clustering. It is based on grouping clusters in bottom-up fashion (agglomerative clustering), at each step combining two clusters that contain the closest pair of el ...
: a simple agglomerative clustering algorithm
**
SUBCLU: a subspace clustering algorithm
**
WACA clustering algorithm: a local clustering algorithm with potentially multi-hop structures; for dynamic networks
**
Ward's method: an agglomerative clustering algorithm, extended to more general Lance–Williams algorithms
*
Estimation Theory
Estimation theory is a branch of statistics that deals with estimating the values of Statistical parameter, parameters based on measured empirical data that has a random component. The parameters describe an underlying physical setting in such ...
**
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
Medical imaging is the technique and process of imaging the interior of a body for clinical analysis and medical intervention, as well as visual representation of the function of some organs or tissues (physiology). Medical imaging seeks to revea ...
for
positron emission tomography
Positron emission tomography (PET) is a functional imaging technique that uses radioactive substances known as radiotracers to visualize and measure changes in metabolic processes, and in other physiological activities including blood flow, r ...
,
single-photon emission computed tomography
Single-photon emission computed tomography (SPECT, or less commonly, SPET) is a nuclear medicine tomography, tomographic imaging technique using gamma rays. It is very similar to conventional nuclear medicine planar imaging using a gamma camera ...
and
X-ray
An X-ray (also known in many languages as Röntgen radiation) is a form of high-energy electromagnetic radiation with a wavelength shorter than those of ultraviolet rays and longer than those of gamma rays. Roughly, X-rays have a wavelength ran ...
computed tomography.
**
Kalman filter
In statistics and control theory, Kalman filtering (also known as linear quadratic estimation) is an algorithm that uses a series of measurements observed over time, including statistical noise and other inaccuracies, to produce estimates of unk ...
: estimate the state of a linear
dynamic system
In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space, such as in a parametric curve. Examples include the mathematical models that describe the swinging of a clock ...
from a series of noisy measurements
**
Odds algorithm
In decision theory, the odds algorithm (or Bruss algorithm) is a mathematical method for computing optimal strategies for a class of problems that belong to the domain of optimal stopping problems. Their solution follows from the ''odds strategy' ...
(Bruss algorithm) Optimal online search for distinguished value in sequential random input
*
False nearest neighbor algorithm (FNN) estimates
fractal dimension
In mathematics, a fractal dimension is a term invoked in the science of geometry to provide a rational statistical index of complexity detail in a pattern. A fractal pattern changes with the Scaling (geometry), scale at which it is measured.
It ...
*
Hidden Markov model
A hidden Markov model (HMM) is a Markov model in which the observations are dependent on a latent (or ''hidden'') Markov process (referred to as X). An HMM requires that there be an observable process Y whose outcomes depend on the outcomes of X ...
**
Baum–Welch algorithm
In electrical engineering, statistical computing and bioinformatics, the Baum–Welch algorithm is a special case of the expectation–maximization algorithm used to find the unknown parameters of a hidden Markov model (HMM). It makes use of the ...
: computes maximum likelihood estimates and
posterior mode
An estimation procedure that is often claimed to be part of Bayesian statistics is the maximum a posteriori (MAP) estimate of an unknown quantity, that equals the mode of the posterior density with respect to some reference measure, typically ...
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
The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events. This i ...
: 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
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because th ...
**
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, the Newton–Raphson method, also known simply as Newton's 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 ...
used to solve
maximum likelihood
In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed stati ...
equations numerically
*
Yamartino method: calculate an approximation to the standard deviation σθ of wind direction θ during a single pass through the incoming data
*
Ziggurat algorithm
The ziggurat algorithm is an algorithm for pseudo-random number sampling. Belonging to the class of rejection sampling algorithms, it relies on an underlying source of uniformly-distributed random numbers, typically from a pseudo-random number ge ...
: generates random numbers from a non-uniform distribution
Computer science
Computer architecture
*
Tomasulo algorithm
Tomasulo's algorithm is a computer architecture hardware algorithm for dynamic scheduling of instructions that allows out-of-order execution and enables more efficient use of multiple execution units. It was developed by Robert Tomasulo at IBM in 1 ...
: allows sequential instructions that would normally be stalled due to certain dependencies to execute non-sequentially
Computer graphics
*
Binary space partitioning
In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a representa ...
*
Clipping
**
Line clipping
In computer graphics, line clipping is the process of removing ( clipping) lines or portions of lines outside an area of interest (a viewport or view volume). Typically, any part of a line which is outside of the viewing area is removed.
There ...
***
Cohen–Sutherland
***
Cyrus–Beck
***
Fast-clipping
***
Liang–Barsky
***
Nicholl–Lee–Nicholl
** Polygon clipping
***
Sutherland–Hodgman
***
Vatti
***
Weiler–Atherton
*
Contour line
A contour line (also isoline, isopleth, isoquant or isarithm) of a Function of several real variables, function of two variables is a curve along which the function has a constant value, so that the curve joins points of equal value. It is a ...
s and
Isosurface
An isosurface is a three-dimensional analog of an isoline. It is a surface that represents points of a constant value (e.g. pressure, temperature, velocity, density) within a volume of space; in other words, it is a level set of a continuous f ...
s
**
Marching cubes
Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional discrete scalar field (the elements of which are somet ...
: extract a polygonal mesh of an isosurface from a three-dimensional scalar field (sometimes called voxels)
**
Marching squares
In computer graphics, marching squares is an algorithm that generates contour lines, contours for a two-dimensional scalar field (rectangular array data structure, array of individual numerical values). A similar method can be used to contour 2D ...
: generates contour lines for a two-dimensional scalar field
**
Marching tetrahedrons: an alternative to
Marching cubes
Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional discrete scalar field (the elements of which are somet ...
*
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
Global illumination (GI), or indirect illumination, is a group of algorithms used in 3D computer graphics that are meant to add more realistic lighting
Lighting or illumination is the deliberate use of light to achieve practical or aest ...
algorithms: Considers direct illumination and reflection from other objects.
**
Ambient occlusion
In 3D computer graphics, modeling, and animation, ambient occlusion is a shading and rendering technique used to calculate how exposed each point in a scene is to ambient lighting. For example, the interior of a tube is typically more occlude ...
**
Beam tracing Beam tracing is an algorithm to simulate wave propagation.
It was developed in the context of computer graphics to render 3D scenes,
but it has been also used in other similar areas such as acoustics and
electromagnetism simulations.
Beam tracin ...
**
Cone tracing
**
Image-based lighting
**
Metropolis light transport
**
Path tracing
Path tracing is a rendering algorithm in computer graphics that Simulation, simulates how light interacts with Physical object, objects, voxels, and Volumetric_path_tracing, participating media to generate realistic (''physically plausible'') R ...
**
Photon mapping
In computer graphics, photon mapping is a two-pass global illumination rendering algorithm developed by Henrik Wann Jensen between 1995 and 2001Jensen, H. (1996). ''Global Illumination using Photon Maps''. nlineAvailable at: http://graphics.sta ...
**
Radiosity
**
Ray tracing
*
Hidden-surface removal or visual surface determination
**
Newell's algorithm: eliminate polygon cycles in the depth sorting required in hidden-surface removal
**
Painter's algorithm
The painter's algorithm (also depth-sort algorithm and priority fill) is an algorithm for Hidden-surface determination#Visible surface determination, visible surface determination in 3D computer graphics that works on a polygon, polygon-by-polyg ...
: detects visible parts of a 3-dimensional scenery
**
Scanline rendering
Scanline rendering (also scan line rendering and scan-line rendering) is an algorithm for visible surface determination, in 3D computer graphics, that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis. All of ...
: constructs an image by moving an imaginary line over the image
**
Warnock algorithm
The Warnock algorithm is a hidden surface algorithm invented by John Warnock that is typically used in the field of computer graphics.
It solves the problem of rendering a complicated image by recursive subdivision of a scene until areas are ob ...
*
Line drawing: graphical algorithm for approximating a line segment on discrete graphical media.
**
Bresenham's line algorithm
Bresenham's line algorithm is a line drawing algorithm that determines the points of an ''n''-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw li ...
: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses decision variables)
**
DDA line algorithm: plots points of a 2-dimensional array to form a straight line between specified points
**
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
Shading refers to the depiction of depth perception in 3D models (within the field of 3D computer graphics) or illustrations (in visual art) by varying the level of darkness. Shading tries to approximate local behavior of light on the object's ...
**
Gouraud shading
Gouraud shading ( ), named after Henri Gouraud (computer scientist), Henri Gouraud, is an interpolation method used in computer graphics to produce continuous shading of surfaces represented by Polygon mesh, polygon meshes. In practice, Gouraud ...
: an algorithm to simulate the differing effects of light and colour across the surface of an object in 3D computer graphics
**
Phong shading
In 3D computer graphics, Phong shading, Phong interpolation, or normal-vector interpolation shading is an interpolation technique for surface shading invented by computer graphics pioneer Bui Tuong Phong. Phong shading interpolates surface no ...
: an algorithm to interpolate surface normal-vectors for surface shading in 3D computer graphics
*
Slerp
In computer graphics, slerp is shorthand for spherical linear interpolation, introduced by Ken Shoemake in the context of quaternion interpolation for the purpose of animating 3D rotation. It refers to constant-speed motion along a unit-radius gr ...
(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 (public key) encryption:
**
ElGamal
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in th ...
**
Elliptic curve cryptography
Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys to provide equivalent security, compared to cryptosystems based on modula ...
**
MAE1
**
NTRUEncrypt
**
RSA
*
Digital signatures (asymmetric authentication):
**
DSA, and its variants:
***
ECDSA and Deterministic ECDSA
***
EdDSA (Ed25519)
**
RSA
*
Cryptographic hash function
A cryptographic hash function (CHF) is a hash algorithm (a map (mathematics), map of an arbitrary binary string to a binary string with a fixed size of n bits) that has special properties desirable for a cryptography, cryptographic application: ...
s (see also the section on message authentication codes):
**
BLAKE
**
MD5
The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value. MD5 was designed by Ronald Rivest in 1991 to replace an earlier hash function MD4, and was specified in 1992 as Request for Comments, RFC 1321.
MD5 ...
– Note that there is now a method of generating collisions for MD5
**
RIPEMD-160
**
SHA-1
In cryptography, SHA-1 (Secure Hash Algorithm 1) is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States ...
– Note that there is now a method of generating collisions for SHA-1
**
SHA-2
SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression ...
(SHA-224, SHA-256, SHA-384, SHA-512)
**
SHA-3
SHA-3 (Secure Hash Algorithm 3) is the latest member of the Secure Hash Algorithm family of standards, released by NIST on August 5, 2015. Although part of the same series of standards, SHA-3 is internally different from the MD5-like stru ...
(SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)
**
Tiger
The tiger (''Panthera tigris'') is a large Felidae, cat and a member of the genus ''Panthera'' native to Asia. It has a powerful, muscular body with a large head and paws, a long tail and orange fur with black, mostly vertical stripes. It is ...
(TTH), usually used in
Tiger tree hashes
**
WHIRLPOOL
A whirlpool is a body of rotating water produced by opposing currents or a current running into an obstacle. Small whirlpools form when a bath or a sink is draining. More powerful ones formed in seas or oceans may be called maelstroms ( ). ''Vo ...
*
Cryptographically secure pseudo-random number generator
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also referred t ...
s
**
Blum Blum Shub – based on the hardness of
factorization
In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...
**
Fortuna
Fortuna (, equivalent to the Greek mythology, Greek goddess Tyche) is the goddess of fortune and the personification of luck in Religion in ancient Rome, Roman religion who, largely thanks to the Late Antique author Boethius, remained popular thr ...
, intended as an improvement on
Yarrow algorithm
**
Linear-feedback shift register
In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a Linear#Boolean functions, linear function of its previous state.
The most commonly used linear function of single bits is exclusive-or (XOR). Thus, ...
(note: many LFSR-based algorithms are weak or have been broken)
**
Yarrow algorithm
*
Key exchange
**
Diffie–Hellman key exchange
Diffie–Hellman (DH) key exchangeSynonyms of Diffie–Hellman key exchange include:
* Diffie–Hellman–Merkle key exchange
* Diffie–Hellman key agreement
* Diffie–Hellman key establishment
* Diffie–Hellman key negotiation
* Exponential ke ...
**
Elliptic-curve Diffie–Hellman
Elliptic-curve Diffie–Hellman (ECDH) is a key agreement protocol that allows two parties, each having an Elliptic curve, elliptic-curve public–private key pair, to establish a shared secret over an insecure channel. This shared secret may be di ...
(ECDH)
*
Key derivation function
In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function (which typically uses a cr ...
s, often used for
password hashing and
key stretching
In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources (time and possibly space) it takes to test each possible ke ...
**
Argon2
**
bcrypt
bcrypt is a password-hashing function designed by Niels Provos and David Mazières. It is based on the Blowfish (cipher), Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt (cryptography), salt to protect against rain ...
**
PBKDF2
In cryptography, PBKDF1 and PBKDF2 (Password-Based Key Derivation Function 1 and 2) are key derivation functions with a sliding computational cost, used to reduce vulnerability to brute-force attacks.
PBKDF2 is part of RSA Laboratories' Public- ...
**
scrypt
In cryptography, scrypt (pronounced "ess crypt") is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service. The algorithm was specifically designed to make it costly t ...
*
Message authentication code
In cryptography, a message authentication code (MAC), sometimes known as an authentication tag, is a short piece of information used for authentication, authenticating and Data integrity, integrity-checking a message. In other words, it is used t ...
s (symmetric authentication algorithms, which take a key as a parameter):
**
HMAC
In cryptography, an HMAC (sometimes expanded as either keyed-hash message authentication code or hash-based message authentication code) is a specific type of message authentication code (MAC) involving a cryptographic hash function and a se ...
: keyed-hash message authentication
**
Poly1305
Poly1305 is a universal hash family designed by Daniel J. Bernstein in 2002 for use in cryptography.
As with any universal hash family, Poly1305 can be used as a one-time message authentication code to authenticate a single message using a sec ...
**
SipHash
*
Secret sharing
Secret sharing (also called secret splitting) refers to methods for distributing a secrecy, secret among a group, in such a way that no individual holds any intelligible information about the secret, but when a sufficient number of individuals c ...
, secret splitting, key splitting, M of N algorithms
** Blakey's scheme
**
Shamir's secret sharing
*
Symmetric (secret key) encryption:
**
Advanced Encryption Standard
The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.
AES is a variant ...
(AES), winner of
NIST
The National Institute of Standards and Technology (NIST) is an agency of the United States Department of Commerce whose mission is to promote American innovation and industrial competitiveness. NIST's activities are organized into physical s ...
competition, also known as
Rijndael
The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.
AES is a variant ...
**
Blowfish
**
ChaCha20 updated variant of Salsa20
**
Data Encryption Standard
The Data Encryption Standard (DES ) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryp ...
(DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes
**
IDEA
In philosophy and in common usage, an idea (from the Greek word: ἰδέα (idea), meaning 'a form, or a pattern') is the results of thought. Also in philosophy, ideas can also be mental representational images of some object. Many philosophe ...
**
RC4 (cipher)
**
Salsa20
Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the eSTREAM European Union cryptographic validation process by Bernstein. Ch ...
**
Threefish
**
Tiny Encryption Algorithm
In cryptography, the Tiny Encryption Algorithm (TEA) is a block cipher notable for its simplicity of description and implementation, typically a few lines of code. It was designed by David Wheeler (computer scientist), David Wheeler and Roger Ne ...
(TEA)
**
Twofish
In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but it was not selected for standardization. Two ...
*
Post-quantum cryptography
Post-quantum cryptography (PQC), sometimes referred to as quantum-proof, quantum-safe, or quantum-resistant, is the development of cryptographic algorithms (usually public-key algorithms) that are currently thought to be secure against a crypt ...
*
Proof-of-work algorithms
Digital logic
* Boolean minimization
**
Espresso heuristic logic minimizer: a fast algorithm for Boolean function minimization
**
Petrick's method: another algorithm for Boolean simplification
**
Quine–McCluskey algorithm
The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952 and extended by Edward J. McCluskey in 1956. As a gener ...
: also called as Q-M algorithm, programmable method for simplifying the Boolean equations
Machine learning and statistical classification
*
Almeida–Pineda recurrent backpropagation: Adjust a matrix of synaptic weights to generate desired outputs given its inputs
*
ALOPEX: a correlation-based
machine-learning algorithm
*
Association rule learning
Association rule learning is a rule-based machine learning method for discovering interesting relations between variables in large databases. It is intended to identify strong rules discovered in databases using some measures of interestingness.P ...
: discover interesting relations between variables, used in
data mining
Data mining is the process of extracting and finding patterns in massive data sets involving methods at the intersection of machine learning, statistics, and database systems. Data mining is an interdisciplinary subfield of computer science and ...
**
Apriori algorithm
AprioriRakesh Agrawal and Ramakrishnan SrikanFast algorithms for mining association rules Proceedings of the 20th International Conference on Very Large Data Bases, VLDB, pages 487-499, Santiago, Chile, September 1994. is an algorithm for frequent ...
**
Eclat algorithm
**
FP-growth algorithm
**
One-attribute rule
**
Zero-attribute rule
*
Boosting (meta-algorithm)
In machine learning (ML), boosting is an ensemble metaheuristic for primarily reducing bias (as opposed to variance). It can also improve the stability and accuracy of ML classification and regression algorithms. Hence, it is prevalent in supe ...
: Use many weak learners to boost effectiveness
**
AdaBoost
AdaBoost (short for Adaptive Boosting) is a statistical classification meta-algorithm formulated by Yoav Freund and Robert Schapire in 1995, who won the 2003 Gödel Prize for their work. It can be used in conjunction with many types of learnin ...
: adaptive boosting
**
BrownBoost: a boosting algorithm that may be robust to noisy datasets
**
LogitBoost:
logistic regression
In statistics, a logistic model (or logit model) is a statistical model that models the logit, log-odds of an event as a linear function (calculus), linear combination of one or more independent variables. In regression analysis, logistic regres ...
boosting
**
LPBoost:
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
boosting
*
Bootstrap aggregating (bagging): technique to improve stability and classification accuracy
*
Clustering: a class of
unsupervised learning
Unsupervised learning is a framework in machine learning where, in contrast to supervised learning, algorithms learn patterns exclusively from unlabeled data. Other frameworks in the spectrum of supervisions include weak- or semi-supervision, wh ...
algorithms for grouping and bucketing related input vector
*
Computer Vision
Computer vision tasks include methods for image sensor, acquiring, Image processing, processing, Image analysis, analyzing, and understanding digital images, and extraction of high-dimensional data from the real world in order to produce numerical ...
** 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
* k-nearest neighbors (k-NN): a non-parametric 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(n
3) algorithm for parsing context-free grammars in Chomsky normal form
* Earley parser: another O(n
3) 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(n
3) in worst case.
* Inside-outside algorithm: an O(n
3) algorithm for re-estimating production probabilities in probabilistic context-free grammars
* Lexical analysis
* 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
** Simple precedence parser
* Packrat parser: a linear time parsing algorithm supporting some context-free grammars and parsing expression grammars
* Pratt parser
* 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
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 algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong ...
: 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 String (computer science), strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number ...
: 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
** Abraham Lempel, Lempel–Jacob Ziv, Ziv
*** LZ77 and LZ78
*** LZJB, Lempel–Ziv Jeff Bonwick (LZJB)
*** Lempel–Ziv–Markov chain algorithm (LZMA)
*** Lempel–Ziv–Oberhumer (LZO): speed oriented
*** LZRW, Lempel–Ziv Ross Williams (LZRW)
*** Lempel–Ziv–Stac (LZS)
*** Lempel–Ziv–Storer–Szymanski (LZSS)
*** Lempel–Ziv–Welch (LZW)
*** LZWL: syllable-based variant
*** LZX
* 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
* Vector quantization: technique often used in lossy data compression
* Video 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
* Adaptive histogram equalization: histogram equalization which adapts to local changes in contrast - Contrast Enhancement
* Blind deconvolution: image de-blurring algorithm when point spread function is unknown.
* 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.
* Histogram equalization: use histogram to improve image contrast - Contrast Enhancement
* Richardson–Lucy deconvolution: image de-blurring algorithm
* 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
* Chase (algorithm), The Chase
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.
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
{{DEFAULTSORT:Algorithms
Algorithms, *
Mathematics-related lists, Algorithms
Optimization algorithms and methods,