# List of algorithms

From Wikipedia, the free encyclopedia

The following is a **list of algorithms** along with one-line descriptions for each.

## [edit] Combinatorial algorithms

Further information: Combinatorics

### [edit] 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):

### [edit] Graph algorithms

Further information: Graph theory and Category: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.

#### [edit] Graph drawing

Further information: Graph drawing

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

#### [edit] Network theory

Further information: 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

- Link analysis
- 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

#### [edit] 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
- 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

#### [edit] Search

Further information: State space search and Graph search algorithm

- 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
- General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine.
- Iterative deepening depth-first search (IDDFS): a state space search strategy
- 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

#### [edit] Subgraphs

- Bron–Kerbosch algorithm: a technique for finding maximal cliques in an undirected graph
- Strongly connected components

### [edit] Sequence algorithms

Further information: Sequences

#### [edit] 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

#### [edit] Item search

- Linear search: finds an item in an unsorted list
- Selection algorithm: finds the
*k*th 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

#### [edit] Merging

Main article: Merge algorithm

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

#### [edit] Permutations

Further information: 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

#### [edit] 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

#### [edit] Sorting

Main article: Sorting algorithms

This article appears to contradict the article Sorting_algorithm#Comparison_of_algorithms. Please see discussion on the linked talk page. Please do not remove this message until the contradictions are resolved. (March 2011) |

- 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
- Hybrid
- 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
- Unknown class

#### [edit] Subsequences

Further information: Subsequence

- 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

#### [edit] Substrings

Further information: Substring

- 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

## [edit] Computational mathematics

Further information: Computational mathematics

See also: Combinatorial algorithms and Computational science

### [edit] Abstract algebra

Further information: 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.

### [edit] Computer algebra

Further information: 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)

### [edit] Geometry

Main page: Geometric algorithms

Further information: Computational 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
- 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
- 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

- Delaunay triangulation

### [edit] Number theoretic algorithms

Further information: Number theory

- 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:
- 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
- Multiplication algorithms: fast multiplication of two numbers
- Odlyzko–Schönhage algorithm: calculates nontrivial zeroes of the Riemann zeta function
- Primality tests: determining whether a given number is prime

### [edit] Numerical algorithms

Further information: Numerical analysis and List of numerical analysis topics

#### [edit] Elementary and special functions

Further information: 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
*n*th 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

#### [edit] Geometric

- Filtered back-projection: efficiently compute the inverse 2-dimensional Radon transform.
- Level set method (LSM): a numerical technique for tracking interfaces and shapes

#### [edit] Interpolation and extrapolation

Further information: 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
- Spline interpolation: Reduces error with Runge's phenomenon.
- Trigonometric interpolation

#### [edit] Linear algebra

Further information: Numerical linear algebra

- Eigenvalue algorithms
- 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

#### [edit] Monte Carlo

Further information: Monte Carlo method

- 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

#### [edit] Numerical integration

Further information: 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 (French pronunciation: [veʁˈle]): integrate Newton's equations of motion

#### [edit] Root finding

Main article: Root-finding algorithm

- False position method: approximates roots of a function
- Newton's method: finds zeros of functions with calculus
- Secant method: approximates roots of a function

### [edit] Optimization algorithms

Main article: Optimization (mathematics)

- 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
- 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
- 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
- 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

## [edit] Computational science

Further information: Computational science

### [edit] Astronomy

Main article: Astronomical algorithms

- 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

### [edit] Bioinformatics

Further information: Bioinformatics

See also: Sequence alignment algorithms

- 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

### [edit] Geoscience

Further information: Geoscience

- Vincenty's formulae: a fast algorithm to calculate the distance between two latitude/longitude points on an ellipsoid

### [edit] Linguistics

Further information: Computational linguistics and Natural language processing

- 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

### [edit] Medicine

Further information: Medical algorithms

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

### [edit] Physics

Further information: Computational 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

### [edit] Statistics

Further information: Computational 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

- Expectation-maximization algorithm A class of related algorithms for finding maximum likelihood estimates of parameters in probabilistic models
- 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

## [edit] Computer science

Further information: Computer science

### [edit] Computer architecture

Further information: Computer architecture

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

### [edit] Computer graphics

Further information: Computer graphics

- Clipping
- 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.
- 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

### [edit] Cryptography

Further information: Cryptography and Topics in cryptography

- Asymmetric (public key) encryption:
- 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
- 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

### [edit] 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.

### [edit] Machine learning and statistical classification

Further information: Machine Learning and Statistical classification

- ALOPEX: a correlation based machine learning algorithm
- Association rule learning: discover interesting relations between variables, used in Data mining
- 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

### [edit] Programming language theory

Further information: 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

#### [edit] Parsing

Further information: 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 - 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:
- 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

### [edit] Quantum algorithms

Further information: Quantum algorithm

- 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

### [edit] Theory of computation and automata

Further information: Theory of computation

- 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

## [edit] Information theory and signal processing

Main articles: Information theory and Signal processing

### [edit] Coding theory

Further information: Coding theory

#### [edit] Error detection and correction

Further information: Error detection and correction

- BCH Codes
- 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

#### [edit] Lossless compression algorithms

Main page: 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
^{[1]}

- Arithmetic coding: advanced entropy coding
- 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

#### [edit] Lossy compression algorithms

Main page: 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

### [edit] Digital signal processing

Further information: 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
- 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

#### [edit] Image processing

Further information: Image processing

- Connected component labeling: find and label disjoint regions
- Dithering and half-toning
- 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

## [edit] Software engineering

Further information: 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

### [edit] Database algorithms

Further information: Database

- Algorithms for Recovery and Isolation Exploiting Semantics (ARIES): transaction recovery
- Join algorithms

### [edit] Distributed systems algorithms

Further information: Distributed systems

- Bully algorithm: a method for dynamically selecting a coordinator
- Byzantine fault tolerance: good fault tolerance.
- Clock synchronization
- Detection of Process Termination
- Lamport ordering: a partial ordering of events based on the
*happened-before*relation - Mutual exclusion
- 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

### [edit] 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

### [edit] Operating systems algorithms

Further information: Operating systems

- 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

#### [edit] Disk scheduling

Further information: Disk scheduling

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

#### [edit] Networking

Further information: Computer Network

- 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

#### [edit] Process synchronization

Further information: Process synchronization

#### [edit] Scheduling

Further information: Scheduling (computing)

- 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

## [edit] See also

- Warnsdorff's algorithm
- List of data structures
- List of algorithm general topics
- List of terms relating to algorithms and data structures
- Heuristic