General combinatorial algorithms

• Brent's algorithm: finds a cycle in function value iterations using only two iterators^[2]
• Floyd's cycle-finding algorithm: finds a cycle in function value iterations^[3]
• Gale–Shapley algorithm: solves the stable marriage problem^[4]
• Pseudorandom number generators (uniformly distributed—see also List of pseudorandom number generators for other PRNGs with varying degrees of convergence and varying statistical quality):^[5]
  • ACORN generator
  • Blum Blum Shub
  • Lagged Fibonacci generator
  • Linear congruential generator
  • Mersenne Twister

Graph algorithms

• Coloring algorithm: Graph coloring algorithm.
• 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.

Sequence algorithms

Sequence sorting

Main article: Sorting algorithm

This article appears to contradict the article Sorting_algorithm#Comparison_of_algorithms. (March 2011)

• Exchange sorts
  • Bubble sort: for each pair of indices, swap the items if out of order
  • Cocktail shaker sort or bidirectional bubble sort, a bubble sort traversing the list alternately from front to back and back to front
  • Comb sort
  • Gnome sort
  • Odd–even 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
• Humorous or ineffective
  • Bogosort
  • Slowsort
  • Stooge sort
• Hybrid
  • Flashsort
  • Introsort: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level
  • Timsort: adaptative algorithm derived from merge sort and insertion sort. Used in Python 2.3 and up, and Java SE 7.
• Insertion sorts
  • Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there
  • Library sort
  • Patience sorting
  • Shell sort: an attempt to improve insertion sort
  • Tree sort (binary tree sort): build binary tree, then traverse it to create sorted list
  • Cycle sort: in-place with theoretically optimal number of writes
• Merge sorts
  • Merge sort: sort the first and second half of the list separately, then merge the sorted lists
  • Slowsort
  • Strand sort
• Non-comparison sorts
  • Bead sort
  • Bucket sort
  • Burstsort: build a compact, cache efficient burst trie and then traverse it to create sorted output
  • Counting sort
  • Pigeonhole sort
  • Postman sort: variant of Bucket sort which takes advantage of hierarchical structure
  • Radix sort: sorts strings letter by letter
• Selection sorts
  • Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
  • Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list
  • Smoothgamersort
• Other
  • Bitonic sorter
  • Pancake sorting
  • Spaghetti sort
  • Topological sort
• Unknown class
  • Samplesort

Abstract algebra

• 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

• Buchberger's algorithm: finds a Gröbner basis
• Cantor–Zassenhaus algorithm: factor polynomials over finite fields
• Faugère F4 algorithm: finds a Gröbner basis (also mentions the F5 algorithm)
• Gosper's algorithm: find sums of hypergeometric terms that are themselves hypergeometric terms
• Knuth–Bendix completion algorithm: for rewriting rule systems
• Multivariate division algorithm: for polynomials in several indeterminates
• Pollard's kangaroo algorithm (also known as Pollard's lambda algorithm ): an algorithm for solving the discrete logarithm problem
• Polynomial long division: an algorithm for dividing a polynomial by another polynomial of the same or lower degree
• Risch algorithm: an algorithm for the calculus operation of indefinite integration (i.e. finding antiderivatives)

Geometry

• 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
  • Graham scan
  • Quickhull
  • Gift wrapping algorithm or Jarvis march
  • Chan's algorithm
  • Kirkpatrick–Seidel algorithm
• 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
    • Ruppert's algorithm (also known as Delaunay refinement): create quality Delaunay triangulations
    • Chew's second algorithm: create quality constrained 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
  • Voronoi diagrams, geometric dual of Delaunay triangulation
    • Bowyer–Watson algorithm: create voronoi diagram in any number of dimensions
    • Fortune's Algorithm: create voronoi diagram
  • Quasitriangulation

Number theoretic algorithms

• Binary GCD algorithm: Efficient way of calculating GCD.
• Booth's multiplication algorithm
• Chakravala method: a cyclic algorithm to solve indeterminate quadratic equations, including Pell's equation
• Discrete logarithm:
  • Baby-step giant-step
  • Index calculus algorithm
  • Pollard's rho algorithm for logarithms
  • Pohlig–Hellman algorithm
• Euclidean algorithm: computes the greatest common divisor
• Extended Euclidean algorithm: also solves the equation ax + by = c
• Integer factorization: breaking an integer into its prime factors
  • Congruence of squares
  • Dixon's algorithm
  • Fermat's factorization method
  • General number field sieve
  • Lenstra elliptic curve factorization
  • Pollard's p − 1 algorithm
  • Pollard's rho algorithm
  • prime factorization algorithm
  • Quadratic sieve
  • Shor's algorithm
  • Special number field sieve
  • Trial division
• Multiplication algorithms: fast multiplication of two numbers
  • Karatsuba algorithm
  • Schönhage–Strassen algorithm
  • Toom–Cook multiplication
• Modular square root: computing square roots modulo a prime number
  • Tonelli–Shanks algorithm
  • Cipolla's algorithm
  • Berlekamp's root finding algorithm
• Odlyzko–Schönhage algorithm: calculates nontrivial zeroes of the Riemann zeta function
• Lenstra–Lenstra–Lovász algorithm (also known as LLL algorithm): find a short, nearly orthogonal lattice basis in polynomial time
• Primality tests: determining whether a given number is prime
  • AKS primality test
  • Baillie–PSW primality test
  • Fermat primality test
  • Lucas primality test
  • Miller–Rabin primality test
  • Sieve of Atkin
  • Sieve of Eratosthenes
  • Sieve of Sundaram

Numerical algorithms

Optimization algorithms

Hybrid Algorithms

• Alpha–beta pruning: search to reduce number of nodes in minimax algorithm
• Branch and bound
• Bruss algorithm: see odds algorithm
• Chain matrix multiplication
• Combinatorial optimization: optimization problems where the set of feasible solutions is discrete
  • Greedy randomized adaptive search procedure (GRASP): successive constructions of a greedy randomized solution and subsequent iterative improvements of it through a local search
  • Hungarian method: a combinatorial optimization algorithm which solves the assignment problem in polynomial time
• Constraint satisfaction
  • General algorithms for the constraint satisfaction
    • AC-3 algorithm
    • Difference map algorithm
    • Min conflicts algorithm
  • Chaff algorithm: an algorithm for solving instances of the Boolean satisfiability problem
  • Davis–Putnam algorithm: check the validity of a first-order logic formula
  • Davis–Putnam–Logemann–Loveland algorithm (DPLL): an algorithm for deciding the satisfiability of propositional logic formula in conjunctive normal form, i.e. for solving the CNF-SAT problem
  • Exact cover problem
    • Algorithm X: a nondeterministic algorithm
    • Dancing Links: an efficient implementation of Algorithm X
• Cross-entropy method: a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling
• Differential evolution
• Dynamic Programming: problems exhibiting the properties of overlapping subproblems and optimal substructure
• Ellipsoid method: is an algorithm for solving convex optimization problems
• Evolutionary computation: optimization inspired by biological mechanisms of evolution
  • Evolution strategy
  • Gene expression programming
  • Genetic algorithms
    • Fitness proportionate selection – also known as roulette-wheel selection
    • Stochastic universal sampling
    • Truncation selection
    • Tournament selection
  • Memetic algorithm
  • Swarm intelligence
    • Ant colony optimization
    • Bees algorithm: a search algorithm which mimics the food foraging behavior of swarms of honey bees
    • Particle swarm
• Frank-Wolfe algorithm: an iterative first-order optimization algorithm for constrained convex optimization
• Golden-section search: an algorithm for finding the maximum of a real function
• Gradient descent
• Grid Search
• Harmony search (HS): a metaheuristic algorithm mimicking the improvisation process of musicians
• Interior point method
• Linear programming
  • Benson's algorithm: an algorithm for solving linear vector optimization problems
  • Dantzig–Wolfe decomposition: an algorithm for solving linear programming problems with special structure
  • Delayed column generation
  • Integer linear programming: solve linear programming problems where some or all the unknowns are restricted to integer values
    • Branch and cut
    • Cutting-plane method
  • Karmarkar's algorithm: The first reasonably efficient algorithm that solves the linear programming problem in polynomial time.
  • Simplex algorithm: an algorithm for solving linear programming problems
• Line search
• Local search: a metaheuristic for solving computationally hard optimization problems
  • Random-restart hill climbing
  • Tabu search
• Minimax used in game programming
• Nearest neighbor search (NNS): find closest points in a metric space
  • Best Bin First: find an approximate solution to the nearest neighbor search problem in very-high-dimensional spaces
• Newton's method in optimization
• Nonlinear optimization
  • BFGS method: a nonlinear optimization algorithm
  • Gauss–Newton algorithm: an algorithm for solving nonlinear least squares problems
  • Levenberg–Marquardt algorithm: an algorithm for solving nonlinear least squares problems
  • Nelder–Mead method (downhill simplex method): a nonlinear optimization algorithm
• Odds algorithm (Bruss algorithm): Finds the optimal strategy to predict a last specific event in a random sequence event
• Random Search
• Simulated annealing
• Stochastic tunneling
• Subset sum algorithm
• A hybrid HS-LS conjugate gradient algorithm (see https://doi.org/10.1016/j.cam.2023.115304)
• A hybrid BFGS-Like method (see more https://doi.org/10.1016/j.cam.2024.115857)
• Conjugate gradient methods (see more https://doi.org/10.1016/j.jksus.2022.101923)

Astronomy

• Doomsday algorithm: day of the week
• Zeller's congruence is an algorithm to calculate the day of the week for any Julian or Gregorian calendar date
• various Easter algorithms are used to calculate the day of Easter

Bioinformatics

• Basic Local Alignment Search Tool also known as BLAST: an algorithm for comparing primary biological sequence information
• Kabsch algorithm: calculate the optimal alignment of two sets of points in order to compute the root mean squared deviation between two protein structures.
• Velvet: a set of algorithms manipulating de Bruijn graphs for genomic sequence assembly
• Sorting by signed reversals: an algorithm for understanding genomic evolution.
• Maximum parsimony (phylogenetics): an algorithm for finding the simplest phylogenetic tree to explain a given character matrix.
• UPGMA: a distance-based phylogenetic tree construction algorithm.
• Bloom Filter: probabilistic data structure used to test for the existence of an element within a set. Primarily used in bioinformatics to test for the existence of a k-mer in a sequence or sequences.

Geoscience

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

Linguistics

• Lesk algorithm: word sense disambiguation
• Stemming algorithm: a method of reducing words to their stem, base, or root form
• Sukhotin's algorithm: a statistical classification algorithm for classifying characters in a text as vowels or consonants

Medicine

• ESC algorithm for the diagnosis of heart failure
• Manning Criteria for irritable bowel syndrome
• Pulmonary embolism diagnostic algorithms
• Texas Medication Algorithm Project

Physics

• Constraint algorithm: a class of algorithms for satisfying constraints for bodies that obey Newton's equations of motion
• Demon algorithm: a Monte Carlo method for efficiently sampling members of a microcanonical ensemble with a given energy
• Featherstone's algorithm: computes the effects of forces applied to a structure of joints and links
• Ground state approximation
  • Variational method
    • Ritz method
• n-body problems
  • Barnes–Hut simulation: Solves the n-body problem in an approximate way that has the order O(n log n) instead of O(n²) as in a direct-sum simulation.
  • Fast multipole method (FMM): speeds up the calculation of long-ranged forces
• Rainflow-counting algorithm: Reduces a complex stress history to a count of elementary stress-reversals for use in fatigue analysis
• Sweep and prune: a broad phase algorithm used during collision detection to limit the number of pairs of solids that need to be checked for collision
• VEGAS algorithm: a method for reducing error in Monte Carlo simulations
• Glauber dynamics: a method for simulating the Ising Model on a computer

Statistics

• Algorithms for calculating variance: avoiding instability and numerical overflow
• Approximate counting algorithm: allows counting large number of events in a small register
• Bayesian statistics
  • Nested sampling algorithm: a computational approach to the problem of comparing models in Bayesian statistics
• Clustering Algorithms
  • Average-linkage clustering: a simple agglomerative clustering algorithm
  • Canopy clustering algorithm: an unsupervised pre-clustering algorithm related to the K-means algorithm
  • Complete-linkage clustering: a simple agglomerative clustering algorithm
  • DBSCAN: a density based clustering algorithm
  • Expectation-maximization algorithm
  • Fuzzy clustering: a class of clustering algorithms where each point has a degree of belonging to clusters
    • Fuzzy c-means
    • FLAME clustering (Fuzzy clustering by Local Approximation of MEmberships): define clusters in the dense parts of a dataset and perform cluster assignment solely based on the neighborhood relationships among objects
  • KHOPCA clustering algorithm: a local clustering algorithm, which produces hierarchical multi-hop clusters in static and mobile environments.
  • k-means clustering: cluster objects based on attributes into partitions
  • k-means++: a variation of this, using modified random seeds
  • k-medoids: similar to k-means, but chooses datapoints or medoids as centers
  • Linde–Buzo–Gray algorithm: a vector quantization algorithm to derive a good codebook
  • Lloyd's algorithm (Voronoi iteration or relaxation): group data points into a given number of categories, a popular algorithm for k-means clustering
  • OPTICS: a density based clustering algorithm with a visual evaluation method
  • Single-linkage clustering: a simple agglomerative clustering algorithm
  • SUBCLU: a subspace clustering algorithm
  • Ward's method: an agglomerative clustering algorithm, extended to more general Lance–Williams algorithms
  • WACA clustering algorithm: a local clustering algorithm with potentially multi-hop structures; for dynamic networks
• Estimation Theory
  • Expectation-maximization algorithm A class of related algorithms for finding maximum likelihood estimates of parameters in probabilistic models
    • Ordered subset expectation maximization (OSEM): used in medical imaging for positron emission tomography, single-photon emission computed tomography and X-ray computed tomography.
  • Odds algorithm (Bruss algorithm) Optimal online search for distinguished value in sequential random input
  • Kalman filter: estimate the state of a linear dynamic system from a series of noisy measurements
• False nearest neighbor algorithm (FNN) estimates fractal dimension
• Hidden Markov model
  • Baum–Welch algorithm: computes maximum likelihood estimates and posterior mode estimates for the parameters of a hidden Markov model
  • Forward-backward algorithm: a dynamic programming algorithm for computing the probability of a particular observation sequence
  • Viterbi algorithm: find the most likely sequence of hidden states in a hidden Markov model
• Partial least squares regression: finds a linear model describing some predicted variables in terms of other observable variables
• Queuing theory
  • Buzen's algorithm: an algorithm for calculating the normalization constant G(K) in the Gordon–Newell theorem
• RANSAC (an abbreviation for "RANdom SAmple Consensus"): an iterative method to estimate parameters of a mathematical model from a set of observed data which contains outliers
• Scoring algorithm: is a form of Newton's method used to solve maximum likelihood equations numerically
• Yamartino method: calculate an approximation to the standard deviation σθ of wind direction θ during a single pass through the incoming data
• Ziggurat algorithm: generates random numbers from a non-uniform distribution

Computer architecture

• Tomasulo algorithm: allows sequential instructions that would normally be stalled due to certain dependencies to execute non-sequentially

Computer graphics

• Clipping
  • Line clipping
    • Cohen–Sutherland
    • Cyrus–Beck
    • Fast-clipping
    • Liang–Barsky
    • Nicholl–Lee–Nicholl
  • Polygon clipping
    • Sutherland–Hodgman
    • Vatti
    • Weiler–Atherton
• Contour lines and Isosurfaces
  • Marching cubes: extract a polygonal mesh of an isosurface from a three-dimensional scalar field (sometimes called voxels)
  • Marching squares: generates contour lines for a two-dimensional scalar field
  • Marching tetrahedrons: an alternative to Marching cubes
• Discrete Green's Theorem: is an algorithm for computing double integral over a generalized rectangular domain in constant time. It is a natural extension to the summed area table algorithm
• Flood fill: fills a connected region of a multi-dimensional array with a specified symbol
• Global illumination algorithms: Considers direct illumination and reflection from other objects.
  • Ambient occlusion
  • Beam tracing
  • Cone tracing
  • Image-based lighting
  • Metropolis light transport
  • Path tracing
  • Photon mapping
  • Radiosity
  • Ray tracing
• Hidden-surface removal or Visual surface determination
  • Newell's algorithm: eliminate polygon cycles in the depth sorting required in hidden-surface removal
  • Painter's algorithm: detects visible parts of a 3-dimensional scenery
  • Scanline rendering: constructs an image by moving an imaginary line over the image
  • Warnock algorithm
• Line Drawing: graphical algorithm for approximating a line segment on discrete graphical media.
  • 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)
  • Xiaolin Wu's line algorithm: algorithm for line antialiasing.
• Midpoint circle algorithm: an algorithm used to determine the points needed for drawing a circle
• Ramer–Douglas–Peucker algorithm: Given a 'curve' composed of line segments to find a curve not too dissimilar but that has fewer points
• Shading
  • Gouraud shading: an algorithm to simulate the differing effects of light and colour across the surface of an object in 3D computer graphics
  • Phong shading: an algorithm to interpolate surface normal-vectors for surface shading in 3D computer graphics
• Slerp (spherical linear interpolation): quaternion interpolation for the purpose of animating 3D rotation
• Summed area table (also known as an integral image): an algorithm for computing the sum of values in a rectangular subset of a grid in constant time
• Binary space partitioning

Cryptography

• 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
  • bcrypt
  • PBKDF2
  • scrypt
  • Argon2
• 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 Scheme
• Symmetric (secret key) encryption:
  • Advanced Encryption Standard (AES), winner of NIST competition, also known as Rijndael
  • Blowfish
  • Twofish
  • Threefish
  • Data Encryption Standard (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes
  • IDEA
  • RC4 (cipher)
  • Tiny Encryption Algorithm (TEA)
  • Salsa20, and its updated variant ChaCha20
• Post-quantum cryptography
• Proof-of-work algorithms

Digital logic

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

Machine learning and statistical classification

• Almeida–Pineda recurrent backpropagation: Adjust a matrix of synaptic weights to generate desired outputs given its inputs
• ALOPEX: a correlation-based machine-learning algorithm
• Association rule learning: discover interesting relations between variables, used in data mining
  • Apriori algorithm
  • Eclat algorithm
  • FP-growth algorithm
  • One-attribute rule
  • Zero-attribute rule
• Boosting (meta-algorithm): Use many weak learners to boost effectiveness
  • AdaBoost: adaptive boosting
  • BrownBoost: a boosting algorithm that may be robust to noisy datasets
  • LogitBoost: logistic regression boosting
  • LPBoost: linear programming boosting
• Bootstrap aggregating (bagging): technique to improve stability and classification accuracy
• Computer Vision
  • Grabcut based on Graph cuts
• Decision Trees
  • C4.5 algorithm: an extension to ID3
  • ID3 algorithm (Iterative Dichotomiser 3): use heuristic to generate small decision trees
• Clustering: a class of unsupervised learning algorithms for grouping and bucketing related input vector.
  • k-nearest neighbors (k-NN): a method for classifying objects based on closest training examples in the feature space
• Linde–Buzo–Gray algorithm: a vector quantization algorithm used to derive a good codebook
• Locality-sensitive hashing (LSH): a method of performing probabilistic dimension reduction of high-dimensional data
• Neural Network
  • Backpropagation: a supervised learning method which requires a teacher that knows, or can calculate, the desired output for any given input
  • Hopfield net: a Recurrent neural network in which all connections are symmetric
  • Perceptron: the simplest kind of feedforward neural network: a linear classifier.
  • Pulse-coupled neural networks (PCNN): Neural models proposed by modeling a cat's visual cortex and developed for high-performance biomimetic image processing.
  • Radial basis function network: an artificial neural network that uses radial basis functions as activation functions
  • Self-organizing map: an unsupervised network that produces a low-dimensional representation of the input space of the training samples
• Random forest: classify using many decision trees
• Reinforcement learning:
  • Q-learning: learns an action-value function that gives the expected utility of taking a given action in a given state and following a fixed policy thereafter
  • State–Action–Reward–State–Action (SARSA): learn a Markov decision process policy
  • Temporal difference learning
• Relevance-Vector Machine (RVM): similar to SVM, but provides probabilistic classification
• Supervised learning: Learning by examples (labelled data-set split into training-set and test-set)
• Support Vector Machine (SVM): a set of methods which divide multidimensional data by finding a dividing hyperplane with the maximum margin between the two sets
  • Structured SVM: allows training of a classifier for general structured output labels.
• Winnow algorithm: related to the perceptron, but uses a multiplicative weight-update scheme

Programming language theory

• 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

Quantum algorithms

• Deutsch–Jozsa algorithm: criterion of balance for Boolean function
• Grover's algorithm: provides quadratic speedup for many search problems
• Shor's algorithm: provides exponential speedup (relative to currently known non-quantum algorithms) for factoring a number
• Simon's algorithm: provides a provably exponential speedup (relative to any non-quantum algorithm) for a black-box problem

Theory of computation and automata

• 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

Coding theory

Digital signal processing

• 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

Memory allocation and deallocation algorithms

• Buddy memory allocation: an algorithm to allocate memory such with less fragmentation
• Garbage collectors
  • Cheney's algorithm: an improvement on the Semi-space collector
  • Generational garbage collector: Fast garbage collectors that segregate memory by age
  • Mark-compact algorithm: a combination of the mark-sweep algorithm and Cheney's copying algorithm
  • Mark and sweep
  • Semi-space collector: an early copying collector
• Reference counting

Process synchronization

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

Scheduling

• Earliest deadline first scheduling
• Fair-share scheduling
• Least slack time scheduling
• List scheduling
• Multi level feedback queue
• Rate-monotonic scheduling
• Round-robin scheduling
• Shortest job next
• Shortest remaining time
• Top-nodes algorithm: resource calendar management

I/O scheduling

This section needs expansion. You can help by adding to it. (July 2017)