1.3 Search algorithms

• Linear search: finds an item in an unsorted list
• Selection algorithm: finds the kth largest item in a list
• Binary search: locates an item in a sorted list
• Binary search tree
• Breadth first search: traverses a tree level by level
• Depth first search: traverses a tree branch by branch
• Best-first search: traverses a tree 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.

1.4 String searching algorithms

• Knuth-Morris-Pratt algorithm
• Rabin-Karp string search algorithm
• Boyer-Moore string search algorithm

1.5 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

2 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

3 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

4 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

5 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
  • 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
• Other
  • Diffie-Hellman: key exchange

6 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

7 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
• Levenberg-Marquardt algorithm: find minimum of function of several variables
• 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

7.1 Optimization algorithms

• Simplex algorithm: An algorithm for solving the linear programming problem
• Simulated annealing
• Genetic algorithms
• Particle swarm
• Taboo research

7.2 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

8 Number theoretic algorithms

• 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

9 Numerical algebra

• Buchberger's algorithm: finds a Gröbner 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

10 Parsing

• Recursive descent parser: A method of manually constructing a top-down parser from recursive functions
• 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:
  • 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³) algorithm for parsing any context-free grammar
• Earley's algorithm: Another O(n³) algorithm for parsing any context-free grammar

11 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?

12 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

13 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
• Marsullo's algorithm
• MISER algorithm
• 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

Algorithms

<Hide>