List of algorithms

From HandWiki
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

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

  • Quickselect
  • Introselect

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

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

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

Cryptography

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

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

Memory allocation and deallocation algorithms

Networking

Operating systems algorithms

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