Short description: none
Broad definition of the term algorithm
An algorithm is fundamentally a set of rules or defined procedures that is typically designed and used to solve a specific problem or a broad set of problems.
Broadly, algorithms define process(es), sets of rules, or methodologies that are to be followed 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.[1]
The following is a list of well-known algorithms along with one-line descriptions for each.
Automated planning
Combinatorial algorithms
General combinatorial algorithms
Graph algorithms
Graph drawing
- Force-based algorithms (also known as force-directed algorithms or spring-based algorithm)
- Spectral layout
Network theory
- Network analysis
- Flow networks
Routing for graphs
Graph search
Subgraphs
Sequence algorithms
Approximate sequence matching
- Bitap algorithm: fuzzy algorithm that determines if strings are approximately equal.
- Phonetic algorithms
- Daitch–Mokotoff Soundex: a Soundex refinement which allows matching of Slavic and Germanic surnames
- Double Metaphone: an improvement on Metaphone
- Match rating approach: a phonetic algorithm developed by Western Airlines
- Metaphone: an algorithm for indexing words by their sound, when pronounced in English
- NYSIIS: phonetic algorithm, improves on Soundex
- Soundex: a phonetic algorithm for indexing names by sound, as pronounced in English
- String metrics: computes a similarity or dissimilarity (distance) score between two pairs of text strings
- Trigram search: search for text when the exact syntax or spelling of the target object is not precisely known
Selection algorithms
Sequence search
- Linear search: locates an item in an unsorted sequence
- Selection algorithm: finds the kth largest item in a sequence
- Ternary search: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa
- Sorted lists
- Binary search algorithm: locates an item in a sorted sequence
- Fibonacci search technique: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers
- Jump search (or block search): linear search on a smaller subset of the sequence
- 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.
- Uniform binary search: an optimization of the classic binary search algorithm
- Eytzinger binary search: cache friendly binary search algorithm [6]
Sequence merging
- Main page: Merge algorithm
- Simple merge algorithm
- k-way merge algorithm
- Union (merge, with elements on the output not repeated)
Sequence permutations
Sequence combinations
Sequence alignment
Sequence sorting
- Main page: Sorting algorithm
- 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
- 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
- Merge sorts
- Non-comparison sorts
- 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
- Smoothsort
- Other
- Unknown class
Subsequences
Substrings
- 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
- 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 string-search algorithm: amortized linear (sublinear in most times) algorithm for substring search
- Boyer–Moore–Horspool algorithm: Simplification of Boyer–Moore
- 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
- Matching wildcards
Computational mathematics
Abstract algebra
Computer algebra
Geometry
Number theoretic algorithms
Numerical algorithms
Differential equation solving
Elementary and special functions
- Computation of π:
- Division algorithms: for computing quotient and/or remainder of two numbers
- Long division
- Restoring division
- Non-restoring division
- SRT division
- Newton–Raphson division: uses Newton's method to find the reciprocal of D, and multiply that reciprocal by N to find the final quotient Q.
- Goldschmidt division
- Hyperbolic and Trigonometric Functions:
- BKM algorithm: computes elementary functions using a table of logarithms
- CORDIC: computes hyperbolic and trigonometric functions using a table of arctangents
- Exponentiation:
- Addition-chain exponentiation: exponentiation by positive integer powers that requires a minimal number of multiplications
- Exponentiating by squaring: an algorithm used for the fast computation of large integer powers of a number
- Montgomery reduction: an algorithm that allows modular arithmetic to be performed efficiently when the modulus is large
- Multiplication algorithms: fast multiplication of two numbers
- Multiplicative inverse Algorithms: for computing a number's multiplicative inverse (reciprocal).
- Rounding functions: the classic ways to round numbers
- Spigot algorithm: a way to compute the value of a mathematical constant without knowing preceding digits
- Square and Nth root of a number:
- Summation:
- Unrestricted algorithm
Geometric
Interpolation and extrapolation
Linear algebra
Monte Carlo
Numerical integration
Root finding
- Main page: Root-finding algorithm
Optimization algorithms
- Main page: Mathematical optimization
Computational science
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
Medicine
Physics
Statistics
Computer science
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.
- Hidden-surface removal or Visual surface determination
- 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
Cryptography
- Asymmetric (public key) encryption:
- Digital signatures (asymmetric authentication):
- 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
- Key exchange
- Key derivation functions, often used for password hashing and key stretching
- Message authentication codes (symmetric authentication algorithms, which take a key as a parameter):
- Secret sharing, Secret Splitting, Key Splitting, M of N algorithms
- Blakey's Scheme
- Shamir's Scheme
- Symmetric (secret key) encryption:
- Post-quantum cryptography
- Proof-of-work algorithms
Digital logic
Machine learning and statistical classification
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
Parsing
Quantum algorithms
Theory of computation and automata
Information theory and signal processing
- Main pages: Information theory and Signal processing
Coding theory
Error detection and correction
Lossless compression algorithms
Lossy compression algorithms
- 3Dc: a lossy data compression algorithm for normal maps
- Audio and Speech compression
- Image compression
- Block Truncation Coding (BTC): a type of lossy image compression technique for greyscale images
- Embedded Zerotree Wavelet (EZW)
- Fast Cosine Transform algorithms (FCT algorithms): computes Discrete Cosine Transform (DCT) efficiently
- Fractal compression: method used to compress images using fractals
- Set Partitioning in Hierarchical Trees (SPIHT)
- Wavelet compression: form of data compression well suited for image compression (sometimes also video compression and audio compression)
- Transform coding: type of data compression for "natural" data like audio signals or photographic images
- Video compression
- Vector quantization: technique often used in lossy data compression
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
- 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
Image processing
Software engineering
- Cache algorithms
- CHS conversion: converting between disk addressing systems
- Double dabble: Convert binary numbers to BCD
- Hash Function: convert a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index into an array
- Unicode Collation Algorithm
- Xor swap algorithm: swaps the values of two variables without using a buffer
Database algorithms
Distributed systems algorithms
- Clock synchronization
- Consensus (computer science): agreeing on a single value or history among unreliable processors
- Detection of Process Termination
- Dijkstra-Scholten algorithm
- Huang's algorithm
- Lamport ordering: a partial ordering of events based on the happened-before relation
- Leader election: a method for dynamically selecting a coordinator
- Mutual exclusion
- Snapshot algorithm: record a consistent global state for an asynchronous system
- Vector clocks: generate a partial ordering of events in a distributed system and detect causality violations
Memory allocation and deallocation algorithms
Networking
Operating systems algorithms
- Banker's algorithm: algorithm used for deadlock avoidance
- Page replacement algorithms: for selecting the victim page under low memory conditions
Process synchronization
Scheduling
I/O scheduling
Disk scheduling
- Elevator algorithm: Disk scheduling algorithm that works like an elevator.
- Shortest seek first: Disk scheduling algorithm to reduce seek time.
Other
- 'For You' algorithm: a proprietary algorithm developed by the social media network Tik-Tok. Uploaded videos are released first to a selection of users who have been identified by the algorithm as being likely to engage with the video, based on their previous web-site viewing patterns.[10]
See also
References
| Original source: https://en.wikipedia.org/wiki/List of algorithms. Read more |