List of algorithms

An algorithm is a fundamental set of rules or defined procedures that are typically designed and used to be a simpler way to solve a specific problem or a broad set of problems.

Simply speaking, algorithms define different processes, sets of rules and regulations, or methodologies that are to be followed through in calculations, data processing, data mining, pattern recognition, automated reasoning or other problem-solving operations. With the increasing automation of services, more and more decisions are being made by algorithms. Some general examples are risk assessments, anticipatory policing, and pattern recognition technology.

The following is a list of well-known algorithms.

• Brent's algorithm: finds a cycle in function value iterations using only two iterators
• Floyd's cycle-finding algorithm: finds a cycle in function value iterations
• Gale–Shapley algorithm: solves the stable matching problem
• Pseudorandom number generators (uniformly distributed—see also List of pseudorandom number generators for other PRNGs with varying degrees of convergence and varying statistical quality):
  • Blossom algorithm: algorithm for constructing maximum-cardinality matching on graphs.
  • Coloring algorithm: algorithms for graph (vertex or edge) coloring (subject to constraints, e.g. proper coloring or list coloring)
  • 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 lowest common ancestors algorithm: computes lowest common ancestors for pairs of nodes in a tree
  • Topological sort: finds linear order of nodes (e.g. jobs) based on their dependencies.

  Graph drawing

  edit
  • Fisher–Yates shuffle (also known as the Knuth shuffle): randomly shuffle a finite set
  • Heap's permutation generation algorithm: interchange elements to generate next permutation
  • Schensted algorithm: constructs a pair of Young tableaux from a permutation
  • Steinhaus–Johnson–Trotter algorithm (also known as the Johnson–Trotter algorithm): generates permutations by transposing elements

  Sequence combinations

  edit
  • Kadane's algorithm: finds the contiguous subarray with largest sum in an array of numbers
  • Longest common substring problem: find the longest string (or strings) that is a substring (or are substrings) of two or more strings
  • Matching wildcards
    • Krauss matching wildcards algorithm: an open-source non-recursive algorithm
    • Rich Salz' wildmat: a widely used open-source recursive algorithm
  • 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–Horspool algorithm: Simplification of Boyer–Moore
    • Boyer–Moore string-search algorithm: amortized linear (sublinear in most times) algorithm for substring search
    • 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 Boyer–Moore
  • Ukkonen's algorithm: a linear-time, online algorithm for constructing suffix trees

  Computational mathematics

  edit
  • 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.

  Computer algebra

  edit
  • 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
    • Chan's algorithm
    • Gift wrapping algorithm or Jarvis march
    • Graham scan
    • Kirkpatrick–Seidel algorithm
    • Quickhull
  • 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
    • Bentley–Ottmann algorithm
    • Shamos–Hoey 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
  • Nesting algorithm: make the most efficient use of material or space
  • Point in polygon algorithms: tests whether a given point lies within a given polygon
  • Point set registration algorithms: finds the transformation between two point sets to optimally align them.
  • 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
      • Chew's second algorithm: create quality constrained Delaunay triangulations
      • Ruppert's algorithm (also known as Delaunay refinement): create quality 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
    • Quasitriangulation
    • Voronoi diagrams, geometric dual of Delaunay triangulation
      • Bowyer–Watson algorithm: create voronoi diagram in any number of dimensions
      • Fortune's Algorithm: create voronoi diagram

  Number theoretic algorithms

  edit
  • Backward Euler method
  • Euler method
  • Linear multistep methods
  • Multigrid methods (MG methods), a group of algorithms for solving differential equations using a hierarchy of discretizations
  • Partial differential equation:
    • Crank–Nicolson method for diffusion equations
    • Finite difference method
    • Lax–Wendroff for wave equations
  • Runge–Kutta methods
    • Euler integration
  • Trapezoidal rule (differential equations)
  • Verlet integration (French pronunciation:[vɛʁˈlɛ]): integrate Newton's equations of motion

  Elementary and special functions

  edit
  • Bisection method
  • False position method: and Illinois method: 2-point, bracketing
  • Halley's method: uses first and second derivatives
  • ITP method: minmax optimal and superlinear convergence simultaneously
  • Muller's method: 3-point, quadratic interpolation
  • Newton's method: finds zeros of functions with calculus
  • Ridder's method: 3-point, exponential scaling
  • Secant method: 2-point, 1-sided

  Optimization algorithms

  edit
  • Geohash: a public domain algorithm that encodes a decimal latitude/longitude pair as a hash string
  • Vincenty's formulae: a fast algorithm to calculate the distance between two latitude/longitude points on an ellipsoid

  Linguistics

  edit

  Computer architecture

  edit
  • Asymmetric (public key) encryption:
    • ElGamal
    • Elliptic curve cryptography
    • MAE1
    • NTRUEncrypt
    • RSA
  • Digital signatures (asymmetric authentication):
    • DSA, and its variants:
      • ECDSA and Deterministic ECDSA
      • EdDSA (Ed25519)
    • RSA
  • Cryptographic hash functions (see also the section on message authentication codes):
    • BLAKE
    • MD5 – Note that there is now a method of generating collisions for MD5
    • RIPEMD-160
    • SHA-1 – Note that there is now a method of generating collisions for SHA-1
    • SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
    • SHA-3 (SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)
    • Tiger (TTH), usually used in Tiger tree hashes
    • WHIRLPOOL
  • 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 (note: many LFSR-based algorithms are weak or have been broken)
    • Yarrow algorithm
  • Key exchange
    • Diffie–Hellman key exchange
    • Elliptic-curve Diffie–Hellman (ECDH)
  • Key derivation functions, often used for password hashing and key stretching
    • Argon2
    • bcrypt
    • PBKDF2
    • scrypt
  • Message authentication codes (symmetric authentication algorithms, which take a key as a parameter):
    • HMAC: keyed-hash message authentication
    • Poly1305
    • SipHash
  • Secret sharing, secret splitting, key splitting, M of N algorithms
    • Blakey's scheme
    • Shamir's secret sharing
  • Symmetric (secret key) encryption:
    • Advanced Encryption Standard (AES), winner of NIST competition, also known as Rijndael
    • Blowfish
    • ChaCha20 updated variant of Salsa20
    • Data Encryption Standard (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes
    • IDEA
    • RC4 (cipher)
    • Salsa20
    • Threefish
    • Tiny Encryption Algorithm (TEA)
    • Twofish
  • Post-quantum cryptography
  • Proof-of-work algorithms

  Digital logic

  edit
  • Boolean minimization
    • Espresso heuristic logic minimizer: a fast algorithm for Boolean function minimization
    • Petrick's method: another algorithm for Boolean simplification
    • Quine–McCluskey algorithm: also called the Q-M algorithm, programmable method for simplifying the Boolean equations

  Machine learning and statistical classification

  edit
  • 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: generates optimal code for arithmetic expressions

  Parsing

  edit
• Inside-outside algorithm: an O(n) algorithm for re-estimating production probabilities in probabilistic context-free grammars
• Lexical analysis
• 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:
  • Canonical LR parser
  • LALR (look-ahead LR) parser
  • Operator-precedence parser
  • Simple LR parser
  • Simple precedence parser
• Packrat parser: a linear time parsing algorithm supporting some context-free grammars and parsing expression grammars
• Pratt parser
• Recursive descent parser: a top-down parser suitable for LL(k) grammars
• Shunting-yard algorithm: converts an infix-notation math expression to postfix

• Hopcroft's algorithm, Moore's algorithm, and Brzozowski's algorithm: algorithms for minimizing the number of states in a deterministic finite automaton
• 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

• BCH Codes
  • Berlekamp–Massey algorithm
  • Peterson–Gorenstein–Zierler algorithm
  • Reed–Solomon error correction
• 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
  • Damm algorithm
  • 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

• 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
  • Bluestein's FFT algorithm
  • Bruun's FFT algorithm
  • Cooley–Tukey FFT algorithm
  • Fast Fourier transform
  • Prime-factor FFT algorithm
  • Rader's FFT algorithm
• 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

• Algorithms for Recovery and Isolation Exploiting Semantics (ARIES): transaction recovery
• Join algorithms
  • Block nested loop
  • Hash join
  • Nested loop join
  • Sort-Merge Join
• The Chase

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

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

• List of artificial intelligence algorithms
• List of data structures
• List of machine learning algorithms
• List of pathfinding algorithms
• List of algorithm general topics
• Outline of algorithms
• Heuristic