List of algorithms

If you intend to describe a new algorithm, please read algorithms on Wikipedia first, then add a link to your article and a one-line description here.

Combinatorial algorithms

General combinatorial algorithms

• Floyd's cycle-finding algorithm: finds cycles in iterations
• Pseudorandom number generators (uniformly distributed):
• Blum Blum Shub
• Mersenne twister
• Linear congruential generator
• Lagged Fibonacci generator
• Robinson-Schensted algorithm: generates permutations from pairs of Young tableaux

Graph algorithms

• 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
• Perturbation methods: an algorithm that computes a locally shortest paths in a graph
• 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
• Kruskal's algorithm: finds a minimum spanning tree for a graph
• Prim's algorithm: finds a minimum spanning tree for a graph
• Boruvka's algorithm: finds a minimum spanning tree for a graph
• Ford-Fulkerson algorithm: computes the maximum flow in a graph
• Edmonds-Karp algorithm: implementation of Ford-Fulkerson
• Nonblocking Minimal Spanning Switch say, for a telephone exchange
• Spring based algorithm: algorithm for graph drawing
• Topological sort: finds linear order of nodes(e.g. jobs) based on their dependencies.
• Hungarian algorithm: algorithm for finding a perfect matching
• Coloring algorithm: Graph coloring algorithm.
• Nearest neighbour algorithm.

Search algorithms

• Linear search: finds an item in an unsorted list
• Selection algorithm: finds the kth largest item in a list
• Binary search algorithm: locates an item in a sorted list
• Binary search tree: uses binary tree to maintain elements.
• Breadth-first search: traverses a graph level by level
• Depth-first search: traverses a graph branch by branch
• Best-first search: traverses a graph in the order of likely importance using a priority queue
• A* tree search: special case of best-first search that uses heuristics to improve speed
• Uniform-cost search: a tree search that finds the lowest cost route where costs vary
• 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.
• Hash table: finds an item in an unsorted collection in O(1) time.
• Crazy Turtle Puzzle algorithm

String algorithms

Searching

• Aho-Corasick algorithm: trie based algorithm for finding all matches in dictionary.
• Bitap algorithm: fuzzy algorithm that determines strings are approximately equal.
• Boyer-Moore string search algorithm: amortised linear (sublinear in most times) algorithm
• Knuth-Morris-Pratt algorithm: bypasses reexamination of matched characters
• Rabin-Karp string search algorithm: searches multiple patterns efficiently
• Longest common subsequence problem: Haskell's dynamic programming algorithm
• Longest increasing subsequence problem
• Shortest common supersequence problem
• longest common substring problem
• Kadane's algorithm: finds maximum sub-array of any size
• Boyer-Moore-Horspool algorithm

Approximate matching

• Hirschberg's algorithm: space efficient algorithm for computing edit distance
• Levenshtein edit distance
• Metaphone: an algorithm for indexing words by their sound, when pronounced in English
• Needleman-Wunsch algorithm
• NYSIIS: phonetic algorithm
• Smith-Waterman algorithm
• Soundex

Sorting algorithms

• Binary tree sort
• Bogosort
• Bubble sort: for each pair of indices, swap the items if out of order
• Bucket sort
• Cocktail sort
• Comb sort
• Counting sort
• Gnome sort
• Flashsort
• Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
• Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there
• Library sort
• Merge sort: sort the first and second half of the list separately, then merge the sorted lists
• Pancake sorting
• Pigeonhole 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
• Radix sort: sorts strings letter by letter
• Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list
• Shell sort: an attempt to improve insertion sort
• Smoothsort
• Topological sort

Merge algorithms

• Simple Merge algorithm
• k-way Merge algorithm

Compression algorithms

Lossless compression algorithms

• Burrows-Wheeler transform: preprocessing useful for improving lossless compression
• DEFLATE: lossless data compression
• Delta encoding: aid to compression of data in which sequential data occurs frequently
• Dynamic Markov Compression: Compression using predictive arithmetic coding
• Incremental encoding: delta encoding applied to sequences of strings
• LZW: lossless data compression (Lempel-Ziv-Welch)
• LZ77 (algorithm): LZ77 and LZ78 are the names for the two lossless data compression algorithms
• LZMA: short for Lempel-Ziv-Markov chain-Algorithm
• LZO: data compression algorithm that is focused on speed
• PPM compression algorithm
• Shannon-Fano coding
• Truncated binary encoding
• Run-length encoding: lossless data compression taking advantage of strings of repeated characters
• SEQUITUR algorithm: lossless compression by incremental grammar inference on a string
• EZW (Embedded Zerotree Wavelet)
• Entropy encoding: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols
• 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
• Arithmetic coding: advanced entropy coding
• Range encoding: same as arithmetic coding, but looked at in a slightly different way
• Entropy coding with known entropy characteristics
• Unary coding: code that represents a number n with n ones followed by a zero
• Elias delta|gamma|omega coding: universal code encoding the positive integers
• Fibonacci coding: universal code which encodes positive integers into binary code words
• 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

Lossy compression algorithms

• Linear predictive coding: lossy compression by representing the spectral envelope of a digital signal of speech in compressed form
• A-law algorithm: standard companding algorithm
• Mu-law algorithm: standard analog signal compression or companding algorithm
• Fractal compression: method used to compress images using fractals
• Transform coding: type of data compression for "natural" data like audio signals or photographic images
• Vector quantization: technique often used in lossy data compression
• Wavelet compression: form of data compression well suited for image compression (sometimes also video compression and audio compression)

Computational geometry

• Euclidean Distance Transform - Computes the distance between every point in a grid and a discrete collection of points.
• Fortune's Algorithm: a well-known and simple-to-understand algorithm for computing Voronoi diagrams from a set of sites
• Collision detection algorithms: check for the collision or intersection of two given solids
• 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
• Gilbert-Johnson-Keerthi distance algorithm: determining the smallest distance between two convex shapes.
• Line segment intersection: finding whether lines intersect, usually with a sweep line algorithm
• Bentley-Ottmann algorithm
• Shamos-Hoey algorithm
• Point in polygon algorithms: tests whether a given point lies within a given polygon
• Polygon triangulation algorithms: decompose a polygon into a set of triangles

Computer graphics

• Bresenham's line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses decision variables)
• Line drawing algorithm: graphical algorithm for approximating a line segment on discrete graphical media.
• DDA line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses floating-point math)
• Flood fill: fills a connected region of a multi-dimensional array with a specified symbol
• Xiaolin Wu's line algorithm: algorithm for line antialiasing.
• Painter's algorithm: detects visible parts of a 3-dimensional scenery
• Ray tracing (graphics): realistic image rendering
• Phong shading: an illumination model and an interpolation method in 3D computer graphics
• Gouraud shading: an algorithm to simulate the differing effects of light and colour across the surface of an object in 3D computer graphics
• Scanline rendering: constructs an image by moving an imaginary line over the image
• Global illumination algorithms: Considers direct illumination and reflection from other objects.
• Interpolation: Constructing new data points such as in digital zoom.
• Spline interpolation: Reduces error with Runge's phenomenon.

Computer vision

• In image processing, epitomic analysis can be used to represent an image or video by a smaller image or video which preserves its statistical properties.
• Counting objects in an image: Counts the number of objects in a binary image. Uses the connected-component labeling algorithm to first label each object. Then returns the number of labeled objects.

Cryptographic algorithms

• 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
• Asymmetric (public key) encryption:
• DSA
• ElGamal
• RSA
• NTRUEncrypt
• Cryptographic Message digest functions (hashing functions):
• MD5 – Note that there is now a method of generating collisions for MD5
• RIPEMD-160
• SHA-1
• HMAC: keyed-hash message authentication
• Tiger (TTH), usually used in Tiger tree hashes
• Cryptographically secure pseudo-random number generators
• Blum Blum Shub - based on the hardness of factorization
• Yarrow algorithm
• Fortuna, intended as an improvement on Yarrow algorithm
• Linear feedback shift register
• Secret sharing, Secret Splitting, Key Splitting, M of N algorithms
• Shamir's Scheme
• Blakey's Scheme
• Key exchange
• Diffie-Hellman key exchange

Digital signal processing

• CORDIC: Fast trigonometric function computation technique.
• Rainflow-counting algorithm: Reduces a complex stress history to a count of elementary stress-reversals for use in fatigue analysis
• Osem: algorithm for processing of medical images
• Goertzel algorithm Can be used for DTMF digit decoding.
• Discrete Fourier transform: determines the frequencies contained in a (segment of a) signal
• Fast Fourier transform
• Cooley-Tukey FFT algorithm
• Rader's FFT algorithm
• Bluestein's FFT algorithm
• Bruun's FFT algorithm
• Prime-factor FFT algorithm
• Richardson-Lucy deconvolution: image de-blurring algorithm
• Elser Difference-Map Algorithm: X-Ray diffraction microscopy

Software engineering

• Algorithms for Recovery and Isolation Exploiting Semantics: recovery
• Unicode Collation Algorithm
• CHS conversion: converting between disk addressing systems
• Cyclic redundancy check: calculation of a check word
• Parity: simple/fast error detection technique
• Rayrole's algorithm: resource calendar management

Distributed systems algorithms

• Lamport ordering: a partial ordering of events based on the happened-before relation
• Snapshot algorithm: a snapshot is the process of recording the global state of a system
• Vector clocks: a total ordering of events
• Marzullo's algorithm: distributed clock synchronization
• intersection algorithm: another clock agreement algorithm.
• Byzantine fault tolerance: good fault tolerance.

Memory Allocation and deallocation algorithms

• Boehm garbage collector: Conservative garbage collector
• Buddy memory allocation: Algorithm to allocate memory such that fragmentation is less.
• Generational garbage collector: Fast garbage collectors that segregate memory by age
• Mark and sweep
• Reference counting

Operating systems algorithms

• Banker's algorithm: Algorithm used for deadlock avoidance.
• Page replacement algorithms: Selecting the victim page under low memory conditions.
• Bully algorithm: Selecting new leader among many computers.

Disk scheduling algorithms:

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

Process synchronisation algorithms:

• Peterson's algorithm
• Lamport's Bakery algorithm
• Dekker's algorithm

Scheduling algorithms

• Rate-monotonic scheduling
• Earliest deadline first scheduling
• Fair-share scheduling
• Round-robin scheduling
• Multi level feedback queue
• shortest job next
• shortest remaining time
• Least slack time scheduling
• List scheduling

Electronics and hardware algorithms

• 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 minimization: Fast algorithm for boolean function minimization.

Machine learning algorithms

• Support Vector Machines

Medical algorithms

• Medical algorithm
• Texas Medication Algorithm Project

Neural networks

• Hopfield net
• Backpropagation
• Self-organizing map

Genetic algorithms

• Fitness proportionate selection - also known as roulette-wheel selection
• Truncation selection
• Tournament selection
• Stochastic universal sampling

Numerical algebra

• Buchberger's algorithm: finds a Gröbner basis
• Eigenvalue algorithm
• Exponentiating by squaring: quickly computes powers of numbers and matrices
• Gram-Schmidt process: orthogonalizes a set of vectors
• Knuth-Bendix completion algorithm: for rewriting rule systems
• Multivariate division algorithm: for polynomials in several indeterminates

Number theoretic algorithms

• Discrete logarithm:
• Baby-step giant-step
• Pollard's rho algorithm for logarithms
• Pohlig-Hellman algorithm
• Index calculus algorithm
• Euclidean algorithm: computes the greatest common divisor
• Extended Euclidean algorithm: Also solves the equation ax+by = c.
• Binary gcd algorithm: Efficient way of calculating gcd.
• Integer factorization: breaking an integer into its prime factors
• prime factorization algorithm
• Fermat's factorization method
• Trial division
• Lenstra elliptic curve factorization
• Pollard's rho algorithm
• Pollard's p − 1 algorithm
• Congruence of squares
• Quadratic sieve
• Dixon's algorithm
• Special number field sieve
• General number field sieve
• Multiplication algorithms: fast multiplication of two numbers
• Booth's multiplication algorithm
• Primality tests: determining whether a given number is prime
• AKS primality test
• Miller-Rabin primality test
• Sieve of Eratosthenes
• Sieve of Atkin
• Odlyzko-Schönhage algorithm: calculates nontrivial zeroes of the Riemann zeta function

Numerical algorithms

• Biconjugate gradient method: solves systems of linear equations
• Borwein's algorithm: an algorithm to calculate the value of 1/π
• Dancing Links: finds all solutions to the exact cover problem
• De Boor algorithm: computes splines
• De Casteljau's algorithm: computes Bézier curves
• False position method: approximates roots of a function
• Gauss–Jordan elimination: solves systems of linear equations
• Gauss–Seidel method: solves systems of linear equations iteratively
• Gauss–Legendre algorithm: computes the digits of pi
• Kahan summation algorithm: a more accurate method of summing floating-point numbers
• Levinson recursion: solves equation involving a Toeplitz matrix
• Metropolis–Hastings algorithm: used to generate a sequence of samples from the probability distribution of one or more variables
• MISER algorithm: Monte Carlo simulation, numerical integration
• Newton's method: finds zeros of functions with calculus
• Risch algorithm: Translates indefinite integral to algebraic problem
• Rounding functions: the classic ways to round numbers
• Secant method: approximates roots of a function
• Shifting nth-root algorithm: digit by digit root extraction
• Square root: approximates the square root of a number
• Strassen algorithm: faster matrix multiplication
• Symbolic Cholesky decomposition: Efficient way of storing sparse matrix
• Tridiagonal matrix algorithm (Thomas algorithm): solves systems of tridiagonal equations

Optimization algorithms

• Ant colony optimization
• BFGS method: A nonlinear optimization algorithm
• Branch and bound
• Chain matrix multiplication
• Conjugate gradient
• Differential evolution
• Evolution strategy
• Gauss–Newton algorithm: An algorithm for solving nonlinear least squares problems.
• Genetic algorithms
• Gradient descent
• Interior point method
• Karmarkar's algorithm: The first reasonably efficient algorithm that solves the linear programming problem in polynomial time.
• Levenberg–Marquardt algorithm: An algorithm for solving nonlinear least squares problems.
• Line search
• Local search
• Nelder-Mead method (downhill simplex method): A nonlinear optimization algorithm.
• Newton's method in optimization
• Particle swarm
• Random-restart hill climbing
• Simplex algorithm: An algorithm for solving the linear programming problem
• Simulated annealing
• Stochastic tunneling
• Subset sum algorithm
• Tabu search
• Minimax used in game programming
• Alpha-beta pruning: search to reduce number of nodes in minimax algorithm

Parsing

• Recursive descent parser: A top-down parser suitable for LL(k) 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:
• Operator-precedence parser
• SLR (Simple LR) parser
• LALR (Look-ahead LR) parser
• Canonical LR parser
• Packrat parser: A linear time parsing algorithm supporting some context-free grammars and parsing expression grammars
• CYK algorithm: An O(n³) algorithm for parsing any context-free grammar
• Earley parser: Another O(n³) 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³) in worst case.
• Inside-outside algorithm: An O(n³) algorithm for re-estimating production probabilities in probabilistic context-free grammars

Quantum algorithms

• Grover's algorithm: provides quadratic speedup for many search problems
• Shor's algorithm: provides exponential speedup for factoring a number
• Deutsch-Jozsa algorithm: criterion of balance for Boolean function

Theory of computation and automata

• Powerset construction: Algorithm to convert nondeterministic automaton to deterministic automaton.
• Todd-Coxeter algorithm: Procedure for generating cosets.

Other

• Alpha max plus beta min algorithm: an approximation of the square-root of the sum of two squares.
• Astronomical algorithms
• Baum-Welch algorithm: hidden markov models
• Bit manipulation algorithms: Create bit mask algorithm
• Doomsday algorithm: day of the week
• Schreier-Sims algorithm
• Viterbi algorithm: hidden markov models
• Xor swap algorithm: swaps the values of two variables without using a buffer
• Luhn algorithm: a method of validating identification numbers
• Rutishauser's algorithm
• Stemming algorithm: a method of reducing words to their stem, base, or root form
• Hamming weight (population count): find the number of 1 bits in a binary word
• Heisenman-Drogulous isomoglobic algorithm
• Gerchberg–Saxton algorithm: Phase retrieval algorithm for optical planes
• Shunting yard algorithm: convert an infix-notation math expression to postfix