• 107328  Infos

List of algorithms

    The following is a '''list of the algorithms''' described in Wikipedia See also the list of data structures list of 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 one-line description here

    Combinatorial algorithms

    General combinatorial algorithms

    • Floyd's cycle-finding algorithm: finds cycles in iterations
    • Pseudorandom generator]s: producing (uniform) random variates
      • Mersenne twister
    • Robinson-Schensted algorithm: generates permutations from pairs of Young tableaux

    Graph algorithms

    See main article graph theory
    • 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
    • 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

    Search algorithms

    • Linear search: finds an item in an unsorted list
    • Selection algorithm: finds the kth largest item in a list
    • Binary search: locates an item in a sorted list
    • Binary search tree
    • 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
    • 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

    • Knuth-Morris-Pratt algorithm
    • Rabin-Karp string search algorithm
    • Boyer-Moore string search algorithm
    • Aho-Corasick algorithm

    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
    • 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
    • Huffman coding: simple lossless compression taking advantage of relative character frequencies
    • Incremental encoding: delta encoding applied to sequences of strings
    • LZW: lossless data compression (Lempel-Ziv-Welch)
    • Run-length encoding: lossless data compression taking advantage of strings of repeated characters
    • SEQUITUR algorithm: lossless compression by incremental grammar inference on a string

    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 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)
    • Flood fill: fills a connected region of a multi-dimensional array with a specified symbol
    • Painter's algorithm: detects visible parts of a 3-dimensional scenery
    • Ray tracing: realistic image rendering

    Cryptographic algorithms

    (See also Topics in cryptography for an 'analytical glossary')
    • Symmetric 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
    • Asymmetric encryption or digital signature:
      • DSA
      • ElGamal
      • RSA
      • Diffie-Hellman key exchange
      • NTRUEncrypt
    • Cryptographic Message digest functions:
      • MD5 – Note that there is now a method of generating collisions for MD5
      • RIPEMD-160
      • SHA-1
      • HMAC: keyed-hash message authentication
    • Cryptographically secure pseudo-random generator]s
      • Blum Blum Shub - based on the hardness of factorization
      • Yarrow algorithm
      • Fortuna allegedly an improvement on Yarrow
    • Other
      • Diffie-Hellman: key exchange

    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 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
    • Gauss-Jordan elimination: solves systems of linear equations
    • Gauss-Legendre algorithm: computes the digits of pi
    • Newton's method: finds zeros of functions with calculus
    • Gauss-Newton algorithm: find minimum of function of several variables
    • Jones's period proxy algorithm: factors integers
    • Levenberg-Marquardt algorithm: find minimum of function of several variables
    • MISER algorithm: Monte Carlo simulation numerical integration
    • 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

    Optimization algorithms

    • Simplex algorithm: An algorithm for solving the linear programming problem
    • Simulated annealing
    • Genetic algorithms
    • Particle swarm
    • Tabu search
    • Local search

    Digital signal processing

    • CORDIC: Fast trigonometric function computation technique
    • Fast Fourier transform: determines the frequencies contained in a (segment of a) signal
      • Cooley-Tukey FFT algorithm
    • 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

    Number theoretic algorithms

    • Discrete logarithm:
      • Baby-step giant-step
      • Pollard's rho for logarithms]
      • Pohlig-Hellman algorithm
      • Index calculus algorithm
    • Euclidean algorithm: computes the greatest common divisor
    • Integer factorization: breaking an integer into its prime factors
      • Trial division
      • Lenstra elliptic curve factorization
      • Pollard's rho algorithm
      • Pollard's p-1 algorithm
      • Congruence of squares
      • Quadratic sieve
      • Special field sieve]
      • General field sieve]
      • Jones's period proxy algorithm
    • Multiplication algorithms: fast multiplication of two numbers
    • Primality tests: determining whether a given number is prime
      • AKS primality test
      • Miller-Rabin primality test
      • Sieve of Eratosthenes: produces a list of the first primes

    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

    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 parser
      • LALR parser
      • Canonical LR parser
    • Packrat parser: A linear time parsing algorithm supporting some context-free grammars and parsing expression grammars
    • CYK algorithm: An O(n3) algorithm for parsing any context-free grammar
    • Earley's algorithm: Another O(n3) algorithm for parsing any context-free 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
    • Deutsch-Jozsa algorithm: criterion of balance for Boolean function

    Other

    • Banker's algorithm
    • Baum-Welch algorithm
    • Doomsday algorithm: Day of the week
    • Halt: no one yet knows if this 43-byte C program ever halts
    • Levenberg-Marquardt nonlinear squares fitting algorithm]
    • Marzullo's algorithm: distributed clock synchronization
    • Page replacement algorithms
    • Rainflow-counting algorithm
    • Schreier-Sims algorithm
    • Todd-Coxeter algorithm
    • Viterbi algorithm
    • Xor swap algorithm: swaps the values of two variables without using a buffer