List of algorithms

The following is a list of algorithms along with one-line descriptions for each.
==Combinatorial algorithms==
===General combinatorial algorithms===
* Brent's algorithm: finds cycles in iterations using only two iterators
* Floyd's cycle-finding algorithm: finds cycles in iterations
* Gale–Shapley algorithm: solve the stable marriage problem
* Pseudorandom number generators (uniformly distributed):
** Blum Blum Shub
** Lagged Fibonacci generator
** Linear congruential generator
** Mersenne twister
===Graph algorithms===
* Coloring algorithm: Graph coloring algorithm.
* Hopcroft–Karp algorithm: convert a bipartite graph to a maximum cardinality matching 
* Hungarian algorithm: algorithm for finding a perfect matching
* Prüfer coding: conversion between a labeled tree and its Prüfer sequence
* Tarjan's off-line least common ancestors algorithm: compute lowest common ancestors for pairs of nodes in a tree
* Topological sort: finds linear order of nodes(e.g. jobs) based on their dependencies.
====Graph drawing====
* Force-based algorithms (also known as force-directed algorithms or spring-based algorithm)
* Spectral layout
====Network theory====
* Network analysis
** Link analysis
*** Girvan–Newman algorithm: detect communities in complex systems
*** Web link analysis
**** Hyperlink-Induced Topic Search (HITS) (also known as Hubs and authorities)
**** PageRank
**** TrustRank
**** PRW, PFW
* Flow networks
** Dinic's algorithm: is a strongly polynomial algorithm for computing the maximum flow in a flow network.
** Edmonds–Karp algorithm: implementation of Ford–Fulkerson
** Ford–Fulkerson algorithm: computes the maximum flow in a graph
** Karger's algorithm: a Monte Carlo method to compute the minimum cut of a connected graph
** Push-relabel algorithm: computes a maximum flow in a graph
====Routing====
* Edmonds's algorithm (also known as Chu–Liu/Edmonds's 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: find a simple path of maximum length in a given graph
* Minimum spanning tree
** Boruvka's algorithm
** Kruskal's algorithm
** Prim's algorithm
** Reverse-delete algorithm
* Nonblocking Minimal Spanning Switch say, for a telephone exchange
* Shortest path problem
** Bellman–Ford algorithm: computes shortest paths in a weighted graph (where some of the edge weights may be negative)
** Dijkstra's algorithm: computes shortest paths in a graph with non-negative edge weights
** Floyd–Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph
** Johnson algorithm: All pairs shortest path algorithm in sparse weighted directed graph
** Perturbation methods: an algorithm that computes a locally shortest paths in a graph
* Traveling salesman problem
** Christofides algorithm
** Nearest neighbour algorithm
====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: abandon partial solutions when they are found not to satisfy a complete solution
* Beam search: is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement
* Beam stack search: integrates backtracking with beam search
* Best-first search: traverses a graph in the order of likely importance using a priority queue
* Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph
* Bloom filter: a constant time and memory check to see whether a given element exists in a set. May return a false positive, but never a false negative.
* Breadth-first search: traverses a graph level by level
* D*: an incremental heuristic search algorithm
* Depth-first search: traverses a graph branch by branch
* Iterative deepening depth-first search (IDDFS): a state space search strategy
* Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph
* Uniform-cost search: a tree search that finds the lowest cost route where costs vary
* SSS*: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm
====Subgraphs====
* Bron–Kerbosch algorithm: a technique for finding maximal cliques in an undirected graph
* Strongly connected components
** Cheriyan–Mehlhorn/Gabow algorithm
** Kosaraju's algorithm
** Tarjan's algorithm
===Sequence algorithms===
====Approximate matching====
* Bitap algorithm: fuzzy algorithm that determines if strings are approximately equal.
* Phonetic algorithms
** Daitch–Mokotoff Soundex: a Soundex refinement which allows matching of Slavic and Germanic surnames
** Double Metaphone: an improvement on Metaphone
** Match Rating Approach: a phonetic algorithm developed by Western Airlines
** Metaphone: an algorithm for indexing words by their sound, when pronounced in English
** NYSIIS: phonetic algorithm, improves on Soundex
** Soundex: a phonetic algorithm for indexing names by sound, as pronounced in English
* String metrics: compute a similarity or dissimilarity (distance) score between two pairs of text strings
** Damerau–Levenshtein distance compute 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: sum number of positions which are different
** Jaro–Winkler distance: is a measure of similarity between two strings
** Levenshtein edit distance: compute 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
====Item search====
* Linear search: finds an item in an unsorted list
* Selection algorithm: finds the kth largest item in a list
* Sorted lists
** Binary search algorithm: locates an item in a sorted list
** Fibonacci search technique: search a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers
** Jump search (also called block search)
** Predictive search: binary-like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search.
** Uniform binary search: an optimization of the classic binary search algorithm
* Ternary search: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa
====Merging====
* Simple Merge algorithm
* k-way Merge algorithm
* Union (merge, with elements on the output not repeated)
====Permutations====
* Fisher–Yates shuffle (also known as the Knuth shuffle): randomly shuffle a finite set
* Robinson–Schensted algorithm: generates permutations from pairs of Young tableaux
* Steinhaus–Johnson–Trotter algorithm (also known as the Johnson–Trotter algorithm): generate permutations by transposing elements
====Sequence alignment====
* Dynamic time warping: measure similarity between two sequences which may vary in time or speed
* Hirschberg's algorithm: finds the least cost sequence alignment 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
====Sorting====
* Exchange Sorts
** Bubble sort: for each pair of indices, swap the items if out of order
** Cocktail sort
** Comb sort
** Gnome sort
** Odd-even sort
** Quicksort: 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
** Stooge sort
* Hybrid
** Flashsort
** Introsort: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level
** Timsort: adaptative algorithm derived from merge sort and insertion sort. Used in Python >=2.3 and Java SE 7.
* Insertion sorts
** Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there
** Library sort
** Patience sorting
** Shell sort: an attempt to improve insertion sort
** Tree sort (binary tree sort): build binary tree, then traverse it to create sorted list
** Cycle sort: in-place with theoretically optimal number of writes
* Merge sorts
** Merge sort: sort the first and second half of the list separately, then merge the sorted lists
** Strand sort
* Non-comparison sorts
** Bead sort
** Bucket sort
** Burstsort: 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: 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: pick the smallest of the remaining elements, add it to the end of the sorted list
** Smoothsort
* Other
** Bitonic sorter
** Pancake sorting
** Topological sort
* Unknown class
** Samplesort
====Subsequences====
*Kadane's algorithm: finds maximum sub-array of any size
*Longest common subsequence problem: 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
*Shortest common supersequence problem: Find the shortest supersequence that contains two or more sequences as subsequences
====Substrings====
* Longest common substring problem: find the longest string (or strings) that is a substring (or are substrings) of two or more strings
* Substring search
** Aho–Corasick string matching algorithm: trie based algorithm for finding all substring matches to any of a finite set of strings
** Boyer–Moore string search algorithm: amortized linear (sublinear in most times) algorithm for substring search
** Boyer–Moore–Horspool algorithm: Simplification of Boyer–Moore
** 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 the Boyer–Moore
* Ukkonen's algorithm: a linear-time, online algorithm for constructing suffix trees
==Computational mathematics==
===Abstract algebra===
* Chien search: a recursive algorithm for determining roots of polynomials defined over a finite field
* Schreier–Sims algorithm: computing a base and strong generating set (BSGS) of a permutation group
* Todd–Coxeter algorithm: Procedure for generating cosets.
===Computer algebra===
* Buchberger's algorithm: finds a Gröbner basis
* 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: find sums of hypergeometric terms that are themselves hypergeometric terms
* Knuth–Bendix completion algorithm: for rewriting rule systems
* Multivariate division algorithm: for polynomials 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: 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)
===Geometry===
* Closest pair problem: find the pair of points (from a set of points) with the smallest distance between them
* Collision detection algorithms: check for the collision or intersection of two given solids
* Cone algorithm: identify surface points
* Convex hull algorithms: determining the convex hull of a set of points
** Chan's algorithm
** Gift wrapping algorithm or Jarvis march
** Graham scan
** Kirkpatrick–Seidel algorithm
* 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
* Gilbert–Johnson–Keerthi distance algorithm: determining the smallest distance between two convex 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
** Bentley–Ottmann algorithm
** Shamos–Hoey algorithm
* Minimum bounding box algorithms: find the oriented minimum bounding box enclosing a set of points
* Nearest neighbor search: find the nearest point or points to a query point
* Point in polygon algorithms: tests whether a given point lies within a given polygon
* Rotating calipers: determine all antipodal pairs of points and vertices on a convex polygon or convex hull.
* Shoelace algorithm: determine the area of a polygon whose vertices are described by ordered pairs in the plane
* Triangulation
** Delaunay triangulation
*** Ruppert's algorithm (also known as Delaunay refinement): create quality Delaunay triangulations
*** Chew's second algorithm: create quality constrained Delaunay triangulations
** Marching triangles: reconstruct two-dimensional surface geometry from an unstructured point cloud
** Polygon triangulation algorithms: decompose a polygon into a set of triangles
** Voronoi diagrams, geometric dual of Delaunay triangulation
*** Bowyer–Watson algorithm: 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
* Chakravala method: a cyclic algorithm to solve indeterminate quadratic equations, including Pell's equation
* Discrete logarithm:
** Baby-step giant-step
** Index calculus algorithm
** Pollard's rho algorithm for logarithms
** Pohlig–Hellman algorithm
* Euclidean algorithm: computes the greatest common divisor
* Extended Euclidean algorithm: Also solves the equation ax + by = c.
* Integer factorization: breaking an integer into its prime factors
** Congruence of squares
** Dixon's algorithm
** Fermat's factorization method
** General number field sieve 
** Lenstra elliptic curve factorization
** Pollard's p − 1 algorithm
** Pollard's rho algorithm
** prime factorization algorithm
** Quadratic sieve
** Shor's algorithm
** Special number field sieve
** Trial division
* Multiplication algorithms: fast multiplication of two numbers
** Karatsuba algorithm
** Schönhage–Strassen algorithm
** Toom–Cook multiplication
* Odlyzko–Schönhage algorithm: calculates nontrivial zeroes of the Riemann zeta function
* Primality tests: determining whether a given number is prime
** AKS primality test
** Fermat primality test
** Lucas primality test
** Miller–Rabin primality test
** Sieve of Atkin
** Sieve of Eratosthenes
** Sieve of Sundaram
===Numerical algorithms===
==== Elementary and special functions====
* Computation of π:
** Borwein's algorithm: an algorithm to calculate the value of 1/π
** Gauss–Legendre algorithm: computes the digits of pi
** Bailey–Borwein–Plouffe formula: (BBP formula) a spigot algorithm for the computation of the nth binary digit of π
* Hyperbolic and Trigonometric Functions:
** BKM algorithm: compute elementary functions using a table of logarithms
** CORDIC: compute hyperbolic and trigonometric functions using a table of arctangents
* Exponentiation:
** Addition-chain exponentiation exponentiation by positive integer powers that requires a minimal number of multiplications
** Exponentiating by squaring: an algorithm used for the fast computation of large integer powers of a number
* Montgomery reduction: an algorithm that allows modular arithmetic to be performed efficiently when the modulus is large
* Multiplication algorithms: fast multiplication of two numbers
** Booth's multiplication algorithm: a multiplication algorithm that multiplies two signed binary numbers in two's complement notation
** Fürer's algorithm: an integer multiplication algorithm for very large numbers possessing a very low asymptotic complexity
** Karatsuba algorithm: an efficient procedure for multiplying large numbers
** Schönhage–Strassen algorithm: an asymptotically fast multiplication algorithm for large integers
** Toom–Cook multiplication: (Toom3) a multiplication algorithm for large integers
* Rounding functions: the classic ways to round numbers
* Spigot algorithm: A way to compute the value of a mathematical constant 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
** nth root algorithm
** Shifting nth-root algorithm: digit by digit root extraction
* 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
==== Geometric ====
* Filtered back-projection: efficiently compute the inverse 2-dimensional Radon transform.
* Level set method (LSM): a numerical technique for tracking interfaces and shapes
==== Interpolation and extrapolation ====
* Birkhoff interpolation: an extension of polynomial interpolation
* Cubic interpolation
* Hermite interpolation
* Linear interpolation: 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
** Bicubic interpolation, a generalization of cubic interpolation to two dimensions
** Bilinear interpolation: an extension of linear interpolation for interpolating functions of two variables on a regular grid
** Lanczos resampling ("Lanzosh"): a multivariate interpolation method used to compute new values for any digitally sampled data
** Nearest-neighbor interpolation
** Tricubic interpolation, a generalization of cubic interpolation to three dimensions
* Pareto interpolation: a method of estimating the median and other properties of a population that follows a Pareto distribution.
* Polynomial interpolation
** Neville's algorithm
* Spline interpolation: Reduces error with Runge's phenomenon.
** De Boor algorithm: B-splines
** De Casteljau's algorithm: Bézier splines
* Trigonometric interpolation
==== Linear algebra ====
* Eigenvalue algorithms
** Arnoldi iteration
** Inverse iteration
** Jacobi method
** Lanczos iteration
** QR algorithm
** Rayleigh quotient iteration
* Gram–Schmidt process: orthogonalizes a set of vectors
* Matrix multiplication
** Cannon's algorithm: a distributed algorithm for matrix multiplication especially suitable for computers laid out in an N × N mesh
** Coppersmith–Winograd algorithm: square matrix multiplication
** Freivald's algorithm: a randomized algorithm used to verify matrix multiplication
** Strassen algorithm: faster matrix multiplication
* Solving systems of linear equations
** Biconjugate gradient method: solves systems of linear equations
** Conjugate gradient: an algorithm for the numerical solution of particular systems of linear equations
** Gaussian elimination
** Gauss–Jordan elimination: solves systems of linear equations
** Gauss–Seidel method: solves systems of linear equations iteratively
** Levinson recursion: solves equation involving a Toeplitz matrix
** Stone's method: also known as the strongly implicit procedure or SIP, is an algorithm for solving a sparse linear system of equations
** Successive over-relaxation (SOR): method used to speed up convergence of the Gauss–Seidel method
** Tridiagonal matrix algorithm (Thomas algorithm): solves systems of tridiagonal equations
* Sparse matrix algorithms
** Cuthill–McKee algorithm: reduce the bandwidth of sparse symmetric matrices
** Minimum degree algorithm: permute the rows and columns of a symmetric sparse matrix before applying the Cholesky decomposition
** Symbolic Cholesky decomposition: Efficient way of storing sparse matrix
==== Monte Carlo ====
* Gibbs sampling: generate a sequence of samples from the joint probability distribution of two or more random variables
* Metropolis–Hastings algorithm: used to generate a sequence of samples from the probability distribution of one or more variables
* Wang and Landau algorithm: an extension of Metropolis–Hastings algorithm sampling
==== Numerical integration ====
* MISER algorithm: Monte Carlo simulation, numerical integration
* Multigrid methods: (MG methods): a group of algorithms for solving differential equations using a hierarchy of discretizations
* Verlet integration (): integrate Newton's equations of motion
==== Root finding ====
* False position method: approximates roots of a function
* Newton's method: finds zeros of functions with calculus
* Secant method: approximates roots of a function
===Optimization algorithms===
* Alpha-beta pruning: search to reduce number of nodes in minimax algorithm
* Branch and bound
* Chain matrix multiplication
* Combinatorial optimization: optimization problems where the set of feasible solutions is discrete
** Greedy randomized adaptive search procedure (GRASP): successive constructions of a greedy randomized solution and subsequent iterative improvements of it through a local search
** Hungarian method: a combinatorial optimization algorithm which solves the assignment problem in polynomial time
* Constraint satisfaction
** General algorithms for the constraint satisfaction
*** AC-3 algorithm
*** Difference map algorithm
*** Min conflicts algorithm
** Chaff algorithm: an algorithm for solving instances of the boolean satisfiability problem
** Davis–Putnam algorithm: check the validity of a first-order logic formula 
** Davis–Putnam–Logemann–Loveland algorithm (DPLL): an algorithm for deciding the satisfiability of propositional logic formula in conjunctive normal form, i.e. for solving the CNF-SAT problem
** Exact cover problem
*** Algorithm X: a nondeterministic algorithm
*** Dancing Links: an efficient implementation of Algorithm X
* Cross-entropy method: a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling
* Differential evolution
* Dynamic Programming: problems exhibiting the properties of overlapping subproblems and optimal substructure
* Ellipsoid method: is an algorithm for solving convex optimization problems
* Evolutionary computation: optimization inspired by biological mechanisms of evolution
** Evolution strategy
** Genetic algorithms
*** Fitness proportionate selection - also known as roulette-wheel selection
*** Stochastic universal sampling
*** Truncation selection
*** Tournament selection
** Memetic algorithm
** Swarm intelligence
*** Ant colony optimization
*** Bees algorithm: a search algorithm which mimics the food foraging behavior of swarms of honey bees
*** Particle swarm
* Gradient descent
* Harmony search (HS): a metaheuristic algorithm mimicking the improvisation process of musicians
* Interior point method
* Linear programming
** Dantzig–Wolfe decomposition: an algorithm for solving linear programming problems with special structure
** Delayed column generation
** Integer linear programming: solve linear programming problems where some or all the unknowns are restricted to integer values
*** Branch and cut
*** Cutting-plane method
** Karmarkar's algorithm: The first reasonably efficient algorithm that solves the linear programming problem in polynomial time.
** Simplex algorithm: An algorithm for solving the linear programming problem
* Line search
* Local search: a metaheuristic for solving computationally hard optimization problems
** Random-restart hill climbing
** Tabu search
* Minimax used in game programming
* Nearest neighbor search (NNS): find closest points in a metric space
** Best Bin First: find an approximate solution to the Nearest neighbor search problem in very high dimensional spaces
* Newton's method in optimization
* Nonlinear optimization
** BFGS method: A nonlinear optimization algorithm
** Gauss–Newton algorithm: An algorithm for solving nonlinear least squares problems.
** Levenberg–Marquardt algorithm: An algorithm for solving nonlinear least squares problems.
** Nelder–Mead method (downhill simplex method): A nonlinear optimization algorithm
* Odds algorithm (Bruss algorithm) : Finds the optimal strategy to predict a last specific event in a random sequence event
* Simulated annealing
* Stochastic tunneling
* Subset sum algorithm
==Computational science==
===Astronomy===
* Doomsday algorithm: day of the week
* Zeller's congruence is an algorithm to calculate the day of the week for any Julian or Gregorian calendar date
* various Easter algorithms are used to calculate the day of Easter
===Bioinformatics===
* Basic Local Alignment Search Tool also known as BLAST: an algorithm for comparing primary biological sequence information
* Kabsch algorithm: calculate the optimal alignment of two sets of points in order to compute the root mean squared deviation between two protein structures.
* Velvet: a set of algorithms manipulating de Bruijn graphs for genomic sequence assembly
===Geoscience===
* Vincenty's formulae: a fast algorithm to calculate the distance between two latitude/longitude points on an ellipsoid
===Linguistics===
* Lesk algorithm: word sense disambiguation
* Stemming algorithm: a method of reducing words to their stem, base, or root form
* Sukhotins 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 diagnostic algorithms
* Texas Medication Algorithm Project
===Physics===
* Constraint algorithm: a class of algorithms for satisfying constraints for bodies that obey Newton's equations of motion
* Demon algorithm: a Monte Carlo method for efficiently sampling members of a microcanonical ensemble with a given energy
* Featherstone's algorithm: compute the effects of forces applied to a structure of joints and links
* Fast multipole method (FMM): speed up the calculation of long-ranged forces in the n-body problem
* Rainflow-counting algorithm: Reduces a complex stress history to a count of elementary stress-reversals for use in fatigue analysis
* Sweep and prune: a broad phase algorithm used during collision detection to limit the number of pairs of solids that need to be checked for collision
* VEGAS algorithm: a method for reducing error in Monte Carlo simulations
===Statistics===
* Algorithms for calculating variance: avoiding instability and numerical overflow
* Approximate counting algorithm: Allows counting large number of events in a small register
* Bayesian statistics
** Nested sampling algorithm: a computational approach to the problem of comparing models in Bayesian statistics
* Clustering Algorithms
** Canopy clustering algorithm: an unsupervised clustering algorithm related to the K-means algorithm
** DBSCAN: a density based clustering algorithm
** Expectation-maximization algorithm
** Fuzzy clustering: a class of clustering algorithms where each point has a degree of belonging to clusters
*** Fuzzy c-means
*** FLAME clustering (Fuzzy clustering by Local Approximation of MEmberships): define clusters in the dense parts of a dataset and perform cluster assignment solely based on the neighborhood relationships among objects
** k-means algorithm: cluster objects based on attributes into partitions
** k-medoids: similar to k-means, but chooses datapoints or medoids as centers
** Linde–Buzo–Gray algorithm: a vector quantization algorithm to derive a good codebook
** Lloyd's algorithm (Voronoi iteration or relaxation): group data points into a given number of categories.
** OPTICS: a density based clustering algorithm with a visual evaluation method
** Single-linkage clustering: a simple agglomerative clustering algorithm
** QT clustering: partitions without the number of clusters a priori
* Estimation Theory
** Expectation-maximization algorithm A class of related algorithms for finding maximum likelihood estimates of parameters in probabilistic models
*** Ordered subset expectation maximization (OSEM): used in medical imaging for positron emission tomography, single photon emission computed tomography and X-ray computed tomography.
** Odds algorithm (Bruss algorithm) Optimal online search for distinguished value in sequential random input
** Kalman filter: estimate the state of a dynamic system from a series of noisy measurements
* False nearest neighbor algorithm (FNN) estimates fractal dimension
* Hidden Markov model
** Baum–Welch algorithm: compute maximum likelihood estimates and posterior mode estimates for the parameters of a hidden markov model
** Forward-backward algorithm a dynamic programming algorithm for computing the probability of a particular observation sequence
** Viterbi algorithm: find the most likely sequence of hidden states in a hidden markov model
* Partial least squares regression: finds a linear model describing some predicted variables in terms of other observable variables
* Queuing theory
** Buzen's algorithm: an algorithm for calculating the normalization constant G(K) in the Gordon–Newell theorem
* RANSAC (an abbreviation for "RANdom SAmple Consensus"): an iterative method to estimate parameters of a mathematical model from a set of observed data which contains outliers
* Scoring algorithm: is a form of Newton's method used to solve maximum likelihood equations numerically
* Yamartino method: calculate an approximation to the standard deviation σθ of wind direction θ during a single pass through the incoming data
* Ziggurat algorithm: generate random numbers from a non-uniform distribution
==Computer science==
===Computer architecture===
* Tomasulo algorithm: allows sequential instructions that would normally be stalled due to certain dependencies to execute non-sequentially
===Computer graphics===
* Clipping
** Line clipping
*** Cohen–Sutherland
*** Cyrus–Beck
*** Fast-clipping
*** Liang–Barsky
*** Nicholl–Lee–Nicholl
** Polygon clipping
*** Sutherland–Hodgman
*** Vatti
*** Weiler–Atherton
* Contour lines and Isosurfaces
** Marching cubes: extract a polygonal mesh of an isosurface from a three-dimensional scalar field (sometimes called voxels)
** Marching squares: generate contour lines for a two-dimensional scalar field
** Marching tetrahedrons: an alternative to Marching cubes
* Discrete Green's Theorem: is an algorithm for computing double integral over a generalized rectangular domain in constant time. It is a natural extension to the summed area table algorithm
* Flood fill: fills a connected region of a multi-dimensional array with a specified symbol
* Global illumination algorithms: Considers direct illumination and reflection from other objects.
** Ambient occlusion
** Beam tracing
** Cone tracing
** Image-based lighting
** Metropolis light transport
** Path tracing
** Photon mapping
** Radiosity 
** 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: detects visible parts of a 3-dimensional scenery
** Scanline rendering: constructs an image by moving an imaginary line over the image
** Warnock algorithm
* Line Drawing: graphical algorithm for approximating a line segment on discrete graphical media.
** Bresenham's line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses decision variables)
** DDA line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses floating-point math)
** Xiaolin Wu's line algorithm: algorithm for line antialiasing.
* Midpoint circle algorithm: an algorithm used to determine the points needed for drawing a circle
* Ramer–Douglas–Peucker algorithm: Given a 'curve' composed of line segments to find a curve not too dissimilar but that has fewer points
* Shading
** Gouraud shading: an algorithm to simulate the differing effects of light and colour across the surface of an object in 3D computer graphics
** Phong shading: an illumination model and an interpolation method in 3D computer graphics
* Slerp (spherical linear interpolation): quaternion interpolation for the purpose of animating 3D rotation
* Summed Area Table (also known as an Integral Image): is an algorithm for computing sum of values in a rectangular subset of a grid in constant time
===Cryptography===
* Asymmetric (public key) encryption:
** DSA
** ElGamal
** Elliptic curve cryptography
** NTRUEncrypt
** RSA
* Cryptographic hash functions:
** HMAC: keyed-hash message authentication
** MD5 – Note that there is now a method of generating collisions for MD5
** RIPEMD-160
** SHA-1
** SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
** Tiger (TTH), usually used in Tiger tree hashes
* Cryptographically secure pseudo-random number generators
** Blum Blum Shub - based on the hardness of factorization
** Fortuna, intended as an improvement on Yarrow algorithm
** Linear feedback shift register
** Yarrow algorithm
* Key exchange
** Diffie–Hellman key exchange
*Secret sharing, Secret Splitting, Key Splitting, M of N algorithms
** Blakey's Scheme
** Shamir's Scheme
* Symmetric (secret key) encryption:
** Advanced Encryption Standard (AES), winner of NIST competition, also known as Rijndael
** Blowfish
** Data Encryption Standard (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes
** IDEA
** RC4 (cipher)
** Tiny Encryption Algorithm
===Digital logic===
* Boolean minimization
** Quine–McCluskey algorithm: Also called as Q-M algorithm, programmable method for simplyfying the boolean equations.
** Petrick's method: Another algorithm for boolean simplification.
** Espresso heuristic logic minimizer: Fast algorithm for boolean function minimization.
===Machine learning and statistical classification ===
* ALOPEX: a correlation based machine learning algorithm
* Association rule learning: discover interesting relations between variables, used in Data mining
** Apriori algorithm
** Eclat algorithm
** FP-Growth algorithm
** One-attribute-rule
** Zero-attribute-rule
* Boosting: Use many weak learners to boost effectiveness
** AdaBoost: adaptive boosting
** BrownBoost:a boosting algorithm that may be robust to noisy datasets
** LogitBoost: logistic regression boosting
** LPBoost: linear programming boosting
* Bootstrap aggregating (bagging): technique to improve stability and classification accuracy
* 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 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.
* 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): neural models proposed by modeling a cat's visual cortex and developed for high-performance 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
* Random multinomial logit: classify using repeated multinomial logit analyses
* Reinforcement Learning:
** Q-learning: learn an action-value function that gives the expected utility of taking a given action in a given state and following a fixed policy thereafter
** SARSA (State-Action-Reward-State-Action): learn a Markov decision process policy
** Temporal difference learning
* Relevance Vector Machine (RVM): similar to SVM, but provides probabilistic classification
* Support Vector Machines (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 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 algorithm
* Rete algorithm: an efficient pattern matching algorithm for implementing production rule systems
* Sethi-Ullman algorithm: generate optimal code for arithmetic expressions
====Parsing====
* CYK algorithm: An O(n3) algorithm for parsing context-free grammars in Chomsky normal form
* Earley parser: Another O(n3) algorithm for parsing any context-free grammar
* GLR parser:An algorithm for parsing any context-free grammar by Masaru Tomita. It is tuned for deterministic grammars, on which it performs almost linear time and O(n3) in worst case.
* Inside-outside algorithm: An O(n3) algorithm for re-estimating production probabilities in probabilistic context-free grammars
* LL parser: A relatively simple linear time parsing algorithm for a limited class of context-free grammars
* LR parser: A more complex linear time parsing algorithm for a larger class of context-free grammars. Variants:
** Canonical LR parser
** LALR (Look-ahead LR) parser
** Operator-precedence parser
** SLR (Simple LR) parser
** Simple precedence parser
* Packrat parser: A linear time parsing algorithm supporting some context-free grammars and parsing expression grammars
* Recursive descent parser: A top-down parser suitable for LL(k) grammars
* Shunting yard algorithm: convert 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: provides exponential speedup (relative to currently known non-quantum algorithms) for factoring a number
* Simon's algorithm: provides a provably exponential speedup (relative to any non-quantum algorithm) for a black-box problem
===Theory of computation and automata===
* 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: 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
** 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: simple/fast error detection technique
** Verhoeff algorithm
====Lossless compression algorithms====
* Burrows-Wheeler transform: preprocessing useful for improving lossless compression
* Context tree weighting
* Delta encoding: aid to compression of data in which sequential data occurs frequently
* Dynamic Markov compression: Compression using predictive arithmetic coding
* Dictionary coders
** Byte pair encoding (BPE)
** DEFLATE
** Lempel-Ziv
*** LZ77 and LZ78
*** Lempel-Ziv Jeff Bonwick (LZJB)
*** Lempel-Ziv-Markov chain-Algorithm (LZMA)
*** Lempel-Ziv-Oberhumer (LZO): speed oriented
*** Lempel-Ziv-Storer-Szymanski (LZSS)
*** Lempel–Ziv–Welch (LZW)
*** LZWL: syllable-based variant
*** LZX
*** Lempel-Ziv Ross Williams (LZRW)
* Entropy encoding: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols
** Arithmetic coding: advanced entropy coding
*** Range encoding: same as arithmetic coding, but looked at in a slightly different way
** Huffman coding: simple lossless compression taking advantage of relative character frequencies
*** Adaptive Huffman coding: adaptive coding technique based on Huffman coding
*** Package-Merge: Optimizes Huffman coding subject to a length restriction on code strings
** Shannon-Fano coding
** Shannon-Fano-Elias coding: precursor to arithmetic encoding http://www.ece.msstate.edu/~fowler/Classes/ECE8813/Handouts/shannon_fano_elias.pdf
* 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 codes: encodes positive integers into binary code words
*** Elias delta, gamma, and omega coding
*** Exponential-Golomb coding
*** Fibonacci coding
*** Levenshtein coding
* Fast Efficient & Lossless Image Compression System (FELICS): a lossless image compression algorithm
* Incremental encoding: delta encoding applied to sequences of strings
* 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 maps
* Audio and 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 algorithms (FCT algorithms): compute 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
===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====
* 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 diffraction microscopy
* 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
** SIFT (Scale-invariant feature transform): is an algorithm to detect and describe local features in images.
* GrowCut algorithm: an interactive segmentation algorithm
* Richardson–Lucy deconvolution: image de-blurring algorithm
* Seam carving: content-aware image resizing algorithm
==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 recovery
* Join algorithms
** Block nested loop
** Hash join
** Nested loop join
** Sort-Merge Join
===Distributed systems algorithms===
* Bully algorithm: a method for dynamically selecting a coordinator
* Byzantine fault tolerance: good fault tolerance.
* Clock synchronization
** Berkeley algorithm
** Cristian's algorithm
** Intersection algorithm
** Marzullo's algorithm
* Detection of Process Termination
** Dijkstra-Scholten algorithm
** Huang's algorithm
* Lamport ordering: a partial ordering of events based on the happened-before relation
* Mutual exclusion
** Lamport's Distributed Mutual Exclusion Algorithm
** Maekawa's Algorithm
** Raymond's Algorithm
** Ricart-Agrawala Algorithm
* Paxos algorithm: a family of protocols for solving consensus in a network of unreliable processors
* Snapshot algorithm: record a consistent global state for an asynchronous system
* Vector clocks: generate a partial ordering of events in a distributed system and detect causality violations
===Memory allocation and deallocation algorithms===
* Buddy memory allocation: Algorithm to allocate memory such that fragmentation is less.
* Garbage collectors
** Boehm garbage collector: Conservative garbage collector
** Cheney's algorithm: An improvement on the Semi-space collector
** Generational garbage collector: Fast garbage collectors that segregate memory by age
** Mark-compact algorithm: a combination of the mark-sweep algorithm and Cheney's copying algorithm
** Mark and sweep
** Semi-space collector: An early copying collector
* Reference counting
===Operating systems algorithms===
* Banker's algorithm: Algorithm used for deadlock avoidance.
* Page replacement algorithms: Selecting the victim page under low memory conditions.
** Adaptive replacement cache: better performance than LRU
** Clock with Adaptive Replacement (CAR): is a page replacement algorithm that has performance comparable to Adaptive replacement cache
====Disk scheduling====
* Elevator algorithm: Disk scheduling algorithm that works like an elevator.
* Shortest seek first: Disk scheduling algorithm to reduce seek time.
====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
* Traffic shaping and Rate limiting 
** Leaky bucket
** Token bucket
====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
==See also==
*Warnsdorff's algorithm
*List of data structures
* List of algorithm general topics
* List of terms relating to algorithms and data structures
*Heuristic
==References==
*
Algorithms
de:Liste von Algorithmen
et:Algoritmide loend
fr:Liste des algorithmes
hi:कलन-विधियों की सूची
id:Daftar algoritma
pt:Anexo:Lista de algoritmos
ru:Список алгоритмов
sr:Списак алгоритама
tg:Рӯихати алгоритмҳо
tr:Algoritma listesi
uk:Список алгоритмів