List of algorithms

Last updated • 59 min readFrom Wikipedia, The Free Encyclopedia

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.

Contents

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

Network theory

Routing for graphs

Subgraphs

Sequence algorithms

Approximate sequence matching

Selection algorithms

Sequence merging

  • Simple merge algorithm
  • k-way merge algorithm
  • Union (merge, with elements on the output not repeated)

Sequence permutations

Sequence combinations

Sequence alignment

Sequence sorting

Subsequences

Substrings

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

Optimization algorithms

Hybrid Algorithms

Computational science

Astronomy

Bioinformatics

Geoscience

Linguistics

Medicine

Physics

Statistics

Computer science

Computer architecture

Computer graphics

Cryptography

Digital logic

Machine learning and statistical classification

Programming language theory

Parsing

Quantum algorithms

Theory of computation and automata

Information theory and signal processing

Coding theory

Error detection and correction

Lossless compression algorithms

Lossy compression algorithms

Digital signal processing

Image processing

Software engineering

Database algorithms

Distributed systems algorithms

Memory allocation and deallocation algorithms

Networking

Operating systems algorithms

Process synchronization

Scheduling

I/O scheduling

Disk scheduling

See also

Related Research Articles

<span class="mw-page-title-main">Algorithm</span> Sequence of operations for a task

In mathematics and computer science, an algorithm is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes and deduce valid inferences.

<span class="mw-page-title-main">Binary search</span> Search algorithm finding the position of a target value within a sorted array

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

<span class="mw-page-title-main">Decision problem</span> Yes/no problem in computer science

In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question based on the given input values. An example of a decision problem is deciding with the help of an algorithm whether a given natural number is prime. Another example is the problem, "given two numbers x and y, does x evenly divide y?"

<span class="mw-page-title-main">Hash function</span> Mapping arbitrary data to fixed-size values

A hash function is any function that can be used to map data of arbitrary size to fixed-size values, though there are some hash functions that support variable-length output. The values returned by a hash function are called hash values, hash codes, hash digests, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter-storage addressing.

<span class="mw-page-title-main">Numerical analysis</span> Methods for numerical approximations

Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis. It is the study of numerical methods that attempt to find approximate solutions of problems rather than the exact ones. Numerical analysis finds application in all fields of engineering and the physical sciences, and in the 21st century also the life and social sciences like economics, medicine, business and even the arts. Current growth in computing power has enabled the use of more complex numerical analysis, providing detailed and realistic mathematical models in science and engineering. Examples of numerical analysis include: ordinary differential equations as found in celestial mechanics, numerical linear algebra in data analysis, and stochastic differential equations and Markov chains for simulating living cells in medicine and biology.

<span class="mw-page-title-main">Search algorithm</span> Any algorithm which solves the search problem

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values.

<span class="mw-page-title-main">Linear programming</span> Method to solve optimization problems

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

In numerical analysis, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function f is a number x such that f(x) = 0. As, generally, the zeros of a function cannot be computed exactly nor expressed in closed form, root-finding algorithms provide approximations to zeros. For functions from the real numbers to real numbers or from the complex numbers to the complex numbers, these are expressed either as floating-point numbers without error bounds or as floating-point values together with error bounds. The latter, approximations with error bounds, are equivalent to small isolating intervals for real roots or disks for complex roots.

<span class="mw-page-title-main">Time complexity</span> Estimate of time taken for running an algorithm

In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

<span class="mw-page-title-main">Z-order curve</span> Mapping function that preserves data point locality

In mathematical analysis and computer science, functions which are Z-order, Lebesgue curve, Morton space-filling curve, Morton order or Morton code map multidimensional data to one dimension well preserving locality of the data points. It is named in France after Henri Lebesgue, who studied it in 1904, and named in the United States after Guy Macdonald Morton, who first applied the order to file sequencing in 1966. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used, such as simple one dimensional arrays, binary search trees, B-trees, skip lists or hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree or octree.

<span class="mw-page-title-main">Recursion (computer science)</span> Use of functions that call themselves

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function.

Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values.

In cryptography, Very Smooth Hash (VSH) is a provably secure cryptographic hash function invented in 2005 by Scott Contini, Arjen Lenstra, and Ron Steinfeld. Provably secure means that finding collisions is as difficult as some known hard mathematical problem. Unlike other provably secure collision-resistant hashes, VSH is efficient and usable in practice. Asymptotically, it only requires a single multiplication per log(n) message-bits and uses RSA-type arithmetic. Therefore, VSH can be useful in embedded environments where code space is limited.

In cryptography, SWIFFT is a collection of provably secure hash functions. It is based on the concept of the fast Fourier transform (FFT). SWIFFT is not the first hash function based on the FFT, but it sets itself apart by providing a mathematical proof of its security. It also uses the LLL basis reduction algorithm. It can be shown that finding collisions in SWIFFT is at least as difficult as finding short vectors in cyclic/ideal lattices in the worst case. By giving a security reduction to the worst-case scenario of a difficult mathematical problem, SWIFFT gives a much stronger security guarantee than most other cryptographic hash functions.

The following outline is provided as an overview of, and topical guide to, machine learning:

References

  1. "algorithm". LII / Legal Information Institute. Retrieved 2023-10-26.
  2. Gegenfurtner, Karl R. (1992-12-01). "PRAXIS: Brent's algorithm for function minimization". Behavior Research Methods, Instruments, & Computers. 24 (4): 560–564. doi: 10.3758/BF03203605 . ISSN   1532-5970.
  3. "richardshin.com | Floyd's Cycle Detection Algorithm". 2013-09-30. Retrieved 2023-10-26.
  4. "Eytzinger Binary Search - Algorithmica" . Retrieved 2023-04-09.
  5. "Shannon-Fano-Elias Coding" (PDF). my.ece.msstate.edu. Archived from the original (PDF) on 2021-02-28. Retrieved 2023-10-11.
  6. "Archived copy" (PDF). www.vision.ee.ethz.ch. Archived from the original (PDF) on 21 February 2007. Retrieved 13 January 2022.{{cite web}}: CS1 maint: archived copy as title (link)
  7. "Archived copy" (PDF). Archived from the original (PDF) on 2013-10-06. Retrieved 2013-10-05.{{cite web}}: CS1 maint: archived copy as title (link)