Online Encyclopedia
List of algorithms
The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.
If you intend to describe a new algorithm, please read algorithms on Wikipedia first, then add a link to your article and a oneline description here.
Contents 
Combinatorial algorithms
General combinatorial algorithms
 Floyd's cyclefinding algorithm: finds cycles in iterations
 Pseudorandom number generators: producing statistically random output
Graph algorithms
See main article graph theory
 BellmanFord 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 nonnegative edge weights
 FloydWarshall algorithm: solves the all pairs shortest path problem in a 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
 FordFulkerson algorithm: computes the maximum flow in a graph
 EdmondsKarp algorithm: implementation of FordFulkerson
 Nonblocking Minimal Spanning Switch say, for a telephone exchange
 Spring based algorithm: algorithm for graph drawing
 Topological sort
Search algorithms
 Linear search: finds an item in an unsorted list
 Binary search: locates an item in a sorted list
 Binary search tree
 Breadth first search: traverses a tree level by level
 Depth first search: traverses a tree branch by branch
 Bestfirst search: traverses a tree in the order of likely importance using a priority queue
 A* tree search: special case of bestfirst 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.
 Hash table: finds an item in an unsorted collection in O(1) time.
String searching algorithms
Sort algorithms
 Binary tree sort
 Bogosort: humorous and slow
 Bubble sort: for each pair of indices, swap the items if out of order
 Bucket sort
 Comb sort
 Cocktail sort
 Counting sort
 Gnome sort
 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
 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
 Stupid sort
 Topological sort
Compression algorithms
 Arithmetic coding: advanced entropy coding
 BurrowsWheeler transform: preprocessing useful for lossless compression
 DEFLATE: lossless data compression
 Delta encoding: aid to compression of data in which sequential data occurs frequently
 Huffman coding: simple lossless compression
 Incremental encoding: delta encoding applied to sequences of strings
 LZW: lossless data compression (LempelZivWelch)
 Runlength encoding: lossless data compression
Computational geometry
 Gift wrapping algorithm: determining the convex hull of a set of points
 Graham scan determining the convex hull of a set of points in the plane
 Point in polygon: tests whether a given point lies within a given polygon
Computer graphics
 Bresenham's line algorithm: plots points of a 2dimensional array to form a straight line between 2 specified points (uses decision variables)
 DDA line algorithm : plots points of a 2dimensional array to form a straight line between 2 specified points (uses floatingpoint math)
 Flood fill: fills a connected region of a multidimensional array with a specified symbol
 Painter's algorithm: detects visible parts of a 3dimensional scenery
 Ray tracing: realistic image rendering
Cryptographic algorithms
See also Topics in cryptography for an 'analytical glossary')

Symmetric (secret key) encryption:
 Advanced Encryption Standard (AES), winner of NIST competition
 Blowfish
 Data Encryption Standard (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes
 IDEA
 RC4 (cipher)
 Asymmetric (public key) encryption or digital signature:
 Cryptographic Message digest functions:
 MD5
 RIPEMD160
 SHA1
 HMAC: keyedhash message authentication

Cryptographically secure pseudorandom number generators
 Blum Blum Shub  based on the hardness of factorization
 Yarrow algorithm

Other
 DiffieHellman: key exchange
Distributed systems algorithms
 Lamport ordering: a partial ordering of events based on the happenedbefore relation
 Snapshot algorithm: a snapshot is the process of recording the global state of a system
 Vector ordering : a total ordering of events
Numerical algorithms
See also main article numerical analysis and list of numerical analysis topics
 De Boor algorithm: computes splines.
 De Casteljau's algorithm: computes Bezier curves
 False position method: approximates roots of a function
 GaussJordan elimination: solves systems of linear equations
 GaussLegendre algorithm: computes the digits of pi
 Newton's method: finds zeros of functions with calculus
 Rounding functions: the classic ways to round numbers
 Secant method: approximates roots of a function
 Shifting nthroot algorithm: digit by digit root extraction
 Square root: approximates the square root of a number
Digital signal processing
 CORDIC: Fast trigonometric function computation technique.
 Fast Fourier transform: determines the frequencies contained in a (segment of a) signal
 Rainflowcounting algorithm: Reduces a complex stress history to a count of elementary stressreversals for use in fatigue analysis
 Osem: algorithm for proccesing of medical images
Number theoretic algorithms
 Euclidean algorithm: computes the greatest common divisor
 Integer factorization: breaking an integer into its prime factors
 Multiplication algorithms: fast multiplication of two numbers

Primality tests: determining whether a given number is prime
 AKS primality test
 MillerRabin primality test
 Sieve of Eratosthenes: produces a list of the first primes
Numerical algebra
 Buchberger's algorithm: finds a Grobner basis
 Eigenvalue algorithm
 Exponentiating by squaring: quickly computes powers of numbers and matrices
 GramSchmidt process: orthogonalizes a set of vectors
 KnuthBendix completion algorithm: for rewriting rule systems
 Multivariate division algorithm: for polynomials in several indeterminates
Optimization algorithms
 Simplex algorithm: An algorithm for solving the linear programming problem
 Simulated annealing
Parsing
 Recursive descent parser: A method of manually constructing a topdown parser from recursive functions
 LL parser: A relatively simple linear time parsing algorithm for a limited class of contextfree grammars
 LR parser: A more complex linear time parsing algorithm for a larger class of contextfree grammars. Variants:
 Packrat parser:: A linear time parsing algorithm supporting both contextfree grammars and parsing expression grammars
 CYK algorithm: An O(n^{3}) algorithm for parsing any contextfree grammar
 Earley's algorithm: Another O(n^{3}) algorithm for parsing any contextfree grammar
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. Is a number even or odd?
Quantum algorithms
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 factorizing a number
 DeutschJozsa algorithm: criterion of balance for Boolean function
Other
 Banker's algorithm
 BaumWelch algorithm
 Doomsday algorithm: Day of the week
 Halt: no one yet knows if this 43byte C program ever halts
 LevenbergMarquardt nonlinear least squares fitting algorithm
 Marsullo's algorithm
 MISER algorithm
 Page replacement algorithms
 Rainflowcounting algorithm
 SchreierSims algorithm
 Strassen algorithm
 ToddCoxeter algorithm
 Xor swap algorithm: swaps the values of two variables without using a buffer
Last updated: 10242004 05:10:45