Contents
Jump to navigation
Jump to search
Combinatorial algorithms[edit]
General combinatorial algorithms[edit]
- Brent's algorithm
- Floyd's cycle-finding algorithm
- Gale–Shapley algorithm
- Pseudorandom number generators (uniformly distributed):
Graph algorithms[edit]
- Coloring algorithm
- Hopcroft–Karp algorithm
- Hungarian algorithm
- Prüfer coding
- Tarjan's off-line least common ancestors algorithm
- Topological sort
Graph drawing[edit]
- Force-based algorithms (also known as force-directed algorithms or spring-based algorithm)
- Spectral layout
Network theory[edit]
- Network analysis
- Link analysis
- Girvan–Newman algorithm
- Web link analysis
- Hyperlink-Induced Topic Search (HITS) (also known as Hubs and authorities)
- PageRank
- TrustRank
- Link analysis
- Flow networks
Routing for graphs[edit]
- Edmonds's algorithm
- Euclidean minimum spanning tree
- Euclidean shortest path problem
- Longest path problem
- Minimum spanning tree
- Nonblocking Minimal Spanning Switch
- Shortest path problem
- Transitive closure problem
- Traveling salesman problem
- Warnsdorff's algorithm
Graph search[edit]
- A* Algorithm
- B*
- Backtracking
- Beam search
- Beam stack search
- Best-first search
- Bidirectional search
- Bloom filter
- Breadth-first search
- D*
- Depth-first search
- Dijkstra's algorithm
- General Problem Solver
- Iterative deepening depth-first search
- Jump point search
- Lexicographic breadth-first search
- Uniform-cost search
- SSS*
Subgraphs[edit]
Sequence algorithms[edit]
Approximate sequence matching[edit]
Selection algorithms[edit]
Sequence search[edit]
Sequence merging[edit]
- Simple merge algorithm
- k-way merge algorithm
- Union (merge, with elements on the output not repeated)
Sequence permutations[edit]
- Fisher–Yates shuffle
- Schensted algorithm
- Steinhaus–Johnson–Trotter algorithm
- Heap's permutation generation algorithm
Sequence alignment[edit]
Sequence sorting[edit]
- Exchange Sorts
- Humorous or ineffective
- Hybrid
- Insertion sorts
- Merge sorts
- Non-comparison sorts
- Selection sorts
- Other
- Unknown class
Subsequences[edit]
- Kadane's algorithm
- Longest common subsequence problem
- Longest increasing subsequence problem
- Shortest common supersequence
Substrings[edit]
Computational mathematics[edit]
Abstract algebra[edit]
Computer algebra[edit]
- Buchberger's algorithm
- Cantor–Zassenhaus algorithm
- Faugère F4 algorithm
- Gosper's algorithm
- Knuth–Bendix completion algorithm
- Multivariate division algorithm
- Pollard's kangaroo algorithm
- Polynomial long division
- Risch algorithm
Geometry[edit]
- Closest pair problem
- Collision detection
- Cone algorithm
- Convex hull algorithms
- Euclidean Distance Transform
- Geometric hashing
- Gilbert–Johnson–Keerthi distance algorithm
- Jump-and-Walk algorithm
- Laplacian smoothing
- Line segment intersection
- Minimum bounding box algorithms
- Nearest neighbor search
- Point in polygon
- Point set registration
- Rotating calipers
- Shoelace algorithm
- Triangulation
Number theoretic algorithms[edit]
- Binary GCD algorithm
- Booth's multiplication algorithm
- Chakravala method
- Discrete logarithm:
- Euclidean algorithm
- Extended Euclidean algorithm
- Integer factorization
- Multiplication algorithm
- Modular square root
- Odlyzko–Schönhage algorithm
- Lenstra–Lenstra–Lovász algorithm
- Primality test
Numerical algorithms[edit]
Differential equation solving[edit]
- Euler method
- Backward Euler method
- Trapezoidal rule (differential equations)
- Linear multistep methods
- Runge–Kutta methods
- Multigrid methods
- Partial differential equation:
- Verlet integration
Elementary and special functions[edit]
- Computation of π:
- Division algorithm
- Hyperbolic and Trigonometric Functions:
- Exponentiation:
- Montgomery reduction
- Multiplication algorithm
- Multiplicative inverse Algorithms
- Rounding functions
- Spigot algorithm
- Square and Nth root of a number:
- Summation:
- Unrestricted algorithm
Geometric[edit]
Interpolation and extrapolation[edit]
- Birkhoff interpolation
- Cubic interpolation
- Hermite interpolation
- Lagrange interpolation
- Linear interpolation
- Monotone cubic interpolation
- Multivariate interpolation
- Pareto interpolation
- Polynomial interpolation
- Spline interpolation
- Trigonometric interpolation
Linear algebra[edit]
- Solving systems of linear equations
- Sparse matrix algorithms
Monte Carlo[edit]
Numerical integration[edit]
Root finding[edit]
- Bisection method
- False position method
- Newton's method
- Halley's method
- Secant method
- False position method
- Ridder's method
- Muller's method
Optimization algorithms[edit]
- Alpha-beta pruning
- Branch and bound
- Bruss algorithm: see odds algorithm
- Chain matrix multiplication
- Combinatorial optimization
- Constraint satisfaction
- General algorithms for the constraint satisfaction
- Chaff algorithm
- Davis–Putnam algorithm
- Davis–Putnam–Logemann–Loveland algorithm
- Exact cover problem
- Cross-entropy method
- Differential evolution
- Dynamic Programming
- Ellipsoid method
- Evolutionary computation
- golden section search
- Gradient descent
- Harmony search
- Interior point method
- Linear programming
- Line search
- Local search
- Minimax
- Nearest neighbor search
- Newton's method in optimization
- Nonlinear optimization
- Odds algorithm
- Simulated annealing
- Stochastic tunneling
- Subset sum
Computational science[edit]
Bioinformatics[edit]
- Basic Local Alignment Search Tool
- Kabsch algorithm
- Velvet
- Sorting by signed reversals
- Maximum parsimony (phylogenetics)
- UPGMA
Statistics[edit]
- Algorithms for calculating variance
- Approximate counting algorithm
- Bayesian statistics
- Clustering Algorithms
- Average-linkage clustering
- Canopy clustering algorithm
- Complete-linkage clustering
- DBSCAN
- Expectation-maximization algorithm
- Fuzzy clustering
- KHOPCA clustering algorithm
- k-means clustering
- k-means++
- k-medoids
- Linde–Buzo–Gray algorithm
- Lloyd's algorithm
- OPTICS
- Single-linkage clustering
- SUBCLU
- Ward's method
- WACA clustering algorithm
- Estimation Theory
- False nearest neighbor algorithm
- Hidden Markov model
- Partial least squares regression
- Queuing theory
- RANSAC
- Scoring algorithm
- Yamartino method
- Ziggurat algorithm
Computer science[edit]
Computer architecture[edit]
Computer graphics[edit]
- Clipping
- Contour lines and Isosurfaces
- Discrete Green's Theorem
- Flood fill
- Global illumination
- Hidden surface removal or Visual surface determination
- Line Drawing
- Midpoint circle algorithm
- Ramer–Douglas–Peucker algorithm
- Shading
- Slerp
- Summed area table
Cryptography[edit]
- Asymmetric (public key) encryption:
- Cryptographic hash function
- Cryptographically secure pseudo-random number generator
- Key exchange
- Key derivation function
- Secret sharing
- Blakey's Scheme
- Shamir's Scheme
- Symmetric (secret key) encryption
Digital logic[edit]
- Boolean minimization
Machine learning and statistical classification[edit]
- ALOPEX: a correlation-based machine-learning algorithm
- Association rule learning: discover interesting relations between variables, used in data mining
- 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
- Decision Trees
- C4.5 algorithm: an extension to ID3
- ID3 algorithm (Iterative Dichotomiser 3): Use heuristic to generate small decision trees
- 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: learn 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
- Support Vector Machines (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[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: generate optimal code for arithmetic expressions
Parsing[edit]
- CYK algorithm: An O(n3) algorithm for parsing context-free grammars in Chomsky normal form
- Earley parser: Another O(n3) algorithm for parsing any context-free grammar
- GLR parser:An algorithm for parsing any context-free grammar by Masaru Tomita. It is tuned for deterministic grammars, on which it performs almost linear time and O(n3) in worst case.
- Inside-outside algorithm: An O(n3) algorithm for re-estimating production probabilities in probabilistic context-free 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:
- Packrat parser: A linear time parsing algorithm supporting some context-free grammars and parsing expression grammars
- Recursive descent parser: A top-down parser suitable for LL(k) grammars
- Shunting yard algorithm: convert an infix-notation math expression to postfix
- Pratt parser
- Jasa SEO
- Lexical analysis
Quantum algorithms[edit]
- 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[edit]
- 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
Information theory and signal processing[edit]
Coding theory[edit]
Error detection and correction[edit]
- BCH Codes
- 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
Lossless compression algorithms[edit]
- Burrows–Wheeler transform: preprocessing useful for improving lossless compression
- Context tree weighting
- Delta encoding: aid to compression of data in which sequential data occurs frequently
- Dynamic Markov compression: Compression using predictive arithmetic coding
- Dictionary coders
- Byte pair encoding (BPE)
- DEFLATE
- Lempel–Ziv
- LZ77 and LZ78
- Lempel–Ziv Jeff Bonwick (LZJB)
- Lempel–Ziv–Markov chain algorithm (LZMA)
- Lempel–Ziv–Oberhumer (LZO): speed oriented
- Lempel–Ziv–Stac (LZS)
- Lempel–Ziv–Storer–Szymanski (LZSS)
- Lempel–Ziv–Welch (LZW)
- LZWL: syllable-based variant
- LZX
- Lempel–Ziv Ross Williams (LZRW)
- Entropy encoding: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols
- Arithmetic coding: advanced entropy coding
- Range encoding: same as arithmetic coding, but looked at in a slightly different way
- Huffman coding: simple lossless compression taking advantage of relative character frequencies
- Adaptive Huffman coding: adaptive coding technique based on Huffman coding
- Package-merge algorithm: Optimizes Huffman coding subject to a length restriction on code strings
- Shannon–Fano coding
- Pakar SEO
- Shannon–Fano–Elias coding: precursor to arithmetic encoding<ref>[1]</ref>
- Arithmetic coding: advanced entropy coding
- Entropy coding with known entropy characteristics
- 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
- Truncated binary encoding
- Unary coding: code that represents a number n with n ones followed by a zero
- Universal codes: encodes positive integers into binary code words
- Elias delta, gamma, and omega coding
- Exponential-Golomb coding
- Fibonacci coding
- Levenshtein coding
- Fast Efficient & Lossless Image Compression System (FELICS): a lossless image compression algorithm
- Incremental encoding: delta encoding applied to sequences of strings
- Prediction by partial matching (PPM): an adaptive statistical data compression technique based on context modeling and prediction
- Run-length encoding: lossless data compression taking advantage of strings of repeated characters
- SEQUITUR algorithm: lossless compression by incremental grammar inference on a string
Lossy compression algorithms[edit]
- 3Dc: a lossy data compression algorithm for normal maps
- Audio and Speech compression
- Image Compression
- Transform coding
- Video compression
- Vector quantization
Digital signal processing[edit]
- Adaptive-additive algorithm
- Discrete Fourier transform
- Fast folding algorithm
- Gerchberg–Saxton algorithm
- Goertzel algorithm
- Karplus-Strong string synthesis
Image processing[edit]
- Contrast Enhancement
- Connected-component labeling
- Dithering and half-toning
- Elser difference-map algorithm
- Feature detection
- Richardson–Lucy deconvolution
- Blind deconvolution
- Median filtering
- Seam carving
- Segmentation
Software engineering[edit]
- Cache algorithms
- CHS conversion
- Double dabble
- Hash Function
- Unicode Collation Algorithm
- Xor swap algorithm
Database algorithms[edit]
Distributed systems algorithms[edit]
- Bully algorithm
- Byzantine fault tolerance
- Clock synchronization
- Detection of Process Termination
- Lamport ordering
- Mutual exclusion
- Paxos algorithm
- Snapshot algorithm
- Vector clocks
Memory allocation and deallocation algorithms[edit]
Networking[edit]
Operating systems algorithms[edit]
Process synchronization[edit]
Scheduling[edit]
- 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