- List of algorithms
The following is a

**list of the algorithms**described in Wikipedia. See also thelist of data structures ,list of algorithm general topics andlist of terms relating to algorithms and data structures .If you intend to describe a new

algorithm , please read 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 generator s (uniformly distributed):

**Blum Blum Shub

**Mersenne twister

**Linear congruential generator

**Lagged Fibonacci generator

*Robinson-Schensted algorithm : generates permutations from pairs ofYoung 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 aminimum spanning tree for a graph

*Prim's algorithm : finds aminimum spanning tree for a graph

*Boruvka's algorithm : finds aminimum 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 atelephone exchange

*Spring based algorithm : algorithm forgraph drawing

* Topological sort: finds linear order of nodes(e.g. jobs) based on their dependencies.

*Hungarian algorithm : algorithm for finding a perfectmatching

*Coloring algorithm : Graph coloring algorithm.

*Nearest neighbour algorithm .Search algorithm s*

Linear search : finds an item in an unsorted list

*Selection algorithm : finds the "k"th 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 apriority 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.

* [*http://crazyturtle.sourceforge.net/ Crazy Turtle Puzzle algorithm*]**tring algorithms***

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 algorithm s* 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 sortMerge algorithm s* Simple Merge algorithm

* k-way Merge algorithm

=*

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 : advancedentropy coding

***Range encoding : same asarithmetic 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

=*

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 computingVoronoi diagrams from a set of sites

*Collision detection algorithms: check for the collision or intersection of two given solids

*Convex hull algorithms : determining theconvex 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 asweep 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 trianglesComputer 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 indigital zoom .

*Spline interpolation : Reduces error withRunge'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

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 ofNIST competition, also known asRijndael

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

* CryptographicMessage 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 generator s

**Blum Blum Shub - based on the hardness of factorization

**Yarrow algorithm

** Fortuna, intended as an improvement onYarrow 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 : Fasttrigonometric 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 forDTMF 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 microscopySoftware 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 managementDistributed systems algorithms*

Lamport ordering : apartial order ing 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 : atotal order ing 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 aGrö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 : forrewriting rule systems

*Multivariate division algorithm : forpolynomial s 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 thegreatest 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 algorithm s: fast multiplication of two numbers

*Booth's multiplication algorithm

*Primality test s: 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 theRiemann 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 theexact cover problem

*De Boor algorithm : computes splines

*De Casteljau's algorithm : computesBézier curve s

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

*Kahan summation algorithm : a more accurate method of summing floating-point numbers

*Levinson recursion : solves equation involving aToeplitz 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 withcalculus

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

Ant colony optimization

*BFGS method : Anonlinear optimization algorithm

*Branch and bound

*Chain matrix multiplication

*Conjugate gradient

*Differential evolution

*Evolution strategy

*Gauss–Newton algorithm : An algorithm for solving nonlinearleast squares problems.

*Genetic algorithms

*Gradient descent

*Interior point method

*Karmarkar's algorithm : The first reasonably efficient algorithm that solves thelinear programming problem inpolynomial time .

*Levenberg–Marquardt algorithm : An algorithm for solving nonlinearleast squares problems.

*Line search

* Local search

*Nelder-Mead method (downhill simplex method): Anonlinear optimization algorithm.

*Newton's method in optimization

* Particle swarm

*Random-restart hill climbing

*Simplex algorithm : An algorithm for solving thelinear 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 algorithmParsing *

Recursive descent parser : A top-down parser suitable for LL("k") grammars

*LL parser : A relatively simplelinear time parsing algorithm for a limited class ofcontext-free grammar s

*LR parser : A more complexlinear time parsing algorithm for a larger class ofcontext-free grammar s. Variants:

**Operator-precedence parser

** SLR (Simple LR) parser

** LALR (Look-ahead LR) parser

**Canonical LR parser

*Packrat parser : Alinear time parsing algorithm supporting somecontext-free grammar s andparsing expression grammar s

*CYK algorithm : An O(n^{3}) algorithm for parsing anycontext-free grammar

*Earley parser : Another O(n^{3}) algorithm for parsing anycontext-free grammar

*GLR parser :An algorithm for parsing anycontext-free grammar by Masaru Tomita. It is tuned for deterministic grammars, on which it performs almostlinear time and O(n^{3}) in worst case.

*Inside-outside algorithm : An O(n^{3}) algorithm for re-estimating production probabilities inprobabilistic context-free grammar s"Application of

quantum computation to various categories of problems and 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 algorithm s

*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

*Wikimedia Foundation.
2010.*