List Of Algorithms
The following is a
list of the algorithms
described in Wikipedia. See also the
list of data structures
,
list of algorithm general topics
and
list of terms relating to algorithms and data structures
. If you intend to describe a new
algorithm
, please read algorithms on Wikipedia first, then add a link to your article and a one-line description here.
Combinatorial algorithms
General combinatorial algorithms
Floyd's cycle-finding algorithm
: finds cycles in iterations
Pseudorandom number generators
: producing (uniform) random variates
Mersenne twister
Graph algorithms
See main article
graph theory
Bellman-Ford algorithm
: computes
shortest paths
in a weighted graph (where some of the edge weights may be negative)
Dijkstra's algorithm
: computes
shortest paths
in a graph with non-negative edge weights
Floyd-Warshall algorithm
: solves the all pairs shortest path problem in a weighted, directed graph
Kruskal's algorithm
: finds a
minimum spanning tree
for a graph
Prim's algorithm
: finds a
minimum spanning tree
for a graph
Boruvka's algorithm
: finds a
minimum spanning tree
for a graph
Ford-Fulkerson algorithm
: computes the
maximum flow
in a graph
Edmonds-Karp algorithm
: implementation of Ford-Fulkerson
Nonblocking Minimal Spanning Switch
say, for a
telephone exchange
Spring based algorithm
: algorithm for graph drawing
Topological sort
Search algorithms
Linear search
: finds an item in an unsorted list
Selection algorithm
: finds the
k
th largest item in a list
Binary search
: locates an item in a sorted list
Binary search tree
Breadth-first search
: traverses a graph level by level
Depth-first search
: traverses a graph branch by branch
Best-first search
: traverses a graph in the order of likely importance using a
priority queue
A* tree search
: special case of best-first search
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.
Hash table
: finds an item in an unsorted collection in O(1) time.
String searching algorithms
Knuth-Morris-Pratt algorithm
Rabin-Karp string search algorithm
Boyer-Moore string search algorithm
Aho-Corasick algorithm
Sort algorithms
Binary tree sort
Bogosort
: humorous and slow
Bubble sort
: for each pair of indices, swap the items if out of order
Bucket sort
Comb sort
Cocktail sort
Counting sort
Gnome sort
Heapsort
: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
Insertion sort
: determine where the current item belongs in the list of sorted ones, and insert it there
Merge sort
: sort the first and second half of the list separately, then merge the sorted lists
Pancake sorting
Pigeonhole 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
Radix sort
: sorts strings letter by letter
Selection sort
: pick the smallest of the remaining elements, add it to the end of the sorted list
Shell sort
: an attempt to improve insertion sort
Smoothsort
Stupid sort
Topological sort
Compression algorithms
Arithmetic coding
: advanced entropy coding
Burrows-Wheeler transform
: preprocessing useful for improving lossless compression
DEFLATE
: lossless data compression
Delta encoding
: aid to compression of data in which sequential data occurs frequently
Huffman coding
: simple lossless compression taking advantage of relative character frequencies
Incremental encoding
: delta encoding applied to sequences of strings
LZW
: lossless data compression (Lempel-Ziv-Welch)
Run-length encoding
: lossless data compression taking advantage of strings of repeated characters
SEQUITUR algorithm
: lossless compression by incremental grammar inference on a string
Computational geometry
Gift wrapping algorithm
: determining the
convex hull
of a set of points
Graham scan
determining the
convex hull
of a set of points in the plane
Point in polygon
: tests whether a given point lies within a given polygon
Computer graphics
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)
Flood fill
: fills a connected region of a multi-dimensional array with a specified symbol
Painter's algorithm
: detects visible parts of a 3-dimensional scenery
Ray tracing
: realistic image
rendering
Cryptographic
algorithms
(See also
Topics in cryptography
for an 'analytical glossary')
Symmetric (secret key) encryption
:
Advanced Encryption Standard
(AES), winner of NIST competition
Blowfish
Data Encryption Standard
(DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes
IDEA
RC4 (cipher)
Asymmetric (public key) encryption
or
digital signature
:
DSA
ElGamal
RSA
Diffie-Hellman key exchange
NTRUEncrypt
Cryptographic
Message digest
functions:
MD5
Note that there is now a method of generating collisions for MD5
RIPEMD-160
SHA-1
HMAC
: keyed-hash message authentication
Cryptographically secure pseudo-random number generators
Blum Blum Shub
- based on the hardness of
factorization
Yarrow algorithm
Fortuna
, allegedly an improvement on Yarrow
Other
Diffie-Hellman
: key exchange
Distributed systems
algorithms
Lamport ordering
: a partial ordering of events based on the
happened-before
relation
Snapshot algorithm
: a snapshot is the process of recording the global state of a system
Vector ordering
: a total ordering of events
Numerical algorithms
See also main article
numerical analysis
and
list of numerical analysis topics
De Boor algorithm
: computes
splines
.
De Casteljau's algorithm
: computes
Bezier curves
False position method
: approximates roots of a function
Gauss-Jordan elimination
: solves systems of linear equations
Gauss-Legendre algorithm
: computes the digits of
pi
Newton's method
: finds zeros of functions with
calculus
Gauss-Newton algorithm
: find minimum of function of several variables
Jones's period proxy algorithm
: factors integers
Levenberg-Marquardt algorithm
: find minimum of function of several variables
MISER algorithm
: Monte Carlo simulation, numerical integration
Rounding functions
: the classic ways to round numbers
Secant method
: approximates roots of a function
Shifting nth-root algorithm
: digit by digit root extraction
Square root
: approximates the square root of a number
Strassen algorithm
Optimization algorithms
Simplex algorithm
: An algorithm for solving the linear programming problem
Simulated annealing
Genetic algorithms
Particle swarm
Tabu search
Local search
Digital signal processing
CORDIC
: Fast
trigonometric function
computation technique.
Fast Fourier transform
: determines the frequencies contained in a (segment of a) signal
Cooley-Tukey FFT algorithm
Rainflow-counting algorithm
: Reduces a complex
stress
history to a count of elementary stress-reversals for use in
fatigue
analysis
Osem
: algorithm for proccesing of medical images
Number theoretic
algorithms
Discrete logarithm
:
Baby-step giant-step
Pollard's rho algorithm for logarithms
Pohlig-Hellman algorithm
Index calculus algorithm
Euclidean algorithm
: computes the
greatest common divisor
Integer factorization
: breaking an integer into its
prime
factors
Trial division
Lenstra elliptic curve factorization
Pollard's rho algorithm
Pollard's p-1 algorithm
Congruence of squares
Quadratic sieve
Special number field sieve
General number field sieve
Multiplication algorithms
: fast multiplication of two numbers
Primality tests
: determining whether a given number is
prime
AKS primality test
Miller-Rabin primality test
Sieve of Eratosthenes
: produces a list of the first primes
Numerical algebra
Buchberger's algorithm
: finds a
Grbner basis
Eigenvalue algorithm
Exponentiating by squaring
: quickly computes powers of numbers and matrices
Gram-Schmidt process
: orthogonalizes a set of vectors
Knuth-Bendix completion algorithm
: for
rewriting
rule systems
Multivariate division algorithm
: for
polynomials
in several indeterminates
Parsing
Recursive descent parser
: A
top-down parser
suitable for LL(
k
) 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:
Operator-precedence parser
SLR (Simple LR) parser
LALR (Look-ahead LR) parser
Canonical LR parser
Packrat parser
: A
linear time
parsing algorithm supporting some
context-free grammars
and
parsing expression grammars
CYK algorithm
: An O(n
3
) algorithm for parsing any
context-free grammar
Earley's algorithm
: Another O(n
3
) algorithm for parsing any
context-free grammar
Software engineering
Algorithms for Recovery and Isolation Exploiting Semantics
: recovery
Unicode Collation Algorithm
CHS conversion
: Converting between disk addressing systems
Cyclic redundancy check
: calculation of a check word
Parity
: Simple/fast error detection technique. Is a number even or odd?
Quantum algorithms
Application of
quantum computation
to various categories of problems and algorithms
Grover's algorithm
: provides quadratic speedup for many search problems
Shor's algorithm
: provides exponential speedup for factorizing a number
Deutsch-Jozsa algorithm
: criterion of balance for Boolean function
Other
Banker's algorithm
Baum-Welch algorithm
Doomsday algorithm
: Day of the week
Halt
: no one yet knows if this 43-byte C program ever halts
Levenberg-Marquardt nonlinear least squares fitting algorithm
Marzullo's algorithm
: distributed clock synchronization
Page replacement algorithms
Rainflow-counting algorithm
Schreier-Sims algorithm
Todd-Coxeter algorithm
Viterbi algorithm
Xor swap algorithm
: swaps the values of two variables without using a buffer
<< Previous
Word Browser
Next >>
lynx (web browser)
lynx programming language
l'hpital's rule
lexicology
lake abitibi
ligature
lansing, michigan
leukemia
length
louis ginzberg
left arm unorthodox spin
list of newspapers
louis ix of france
linear b
larousse gastronomique
louis xiv of france
ludwig von kchel
leo computer
laurence of canterbury
leaf by niggle
lemming
leet
lud
lois lane
linker
legendre symbol
laconia incident
lon theremin
linear prediction
leto
la malinche
lusitania
limited stop
laeken european council
limburg
limburg (netherlands)
lech walesa
lucretia mott
leon
ligand
lincos
lascaux
lex luthor
lute
Copyright 2005-2009 OnPedia.com. All Rights Reserved