List of algorithms

The following is a list of the algorithms described in Glasgledius . See also the list of data structures.

If you intend to describe a new algorithm, please read algorithms on Glasgledius first, then add a link to your article and a one-line description here.

• Compression algorithms:
  • Arithmetic coding: advanced entropy coding
  • Burrows-Wheeler transform: preprocessing useful for lossless compression
  • DEFLATE: lossless data compression
  • Huffman coding: simple lossless entropy coding
  • LZW: lossless data compression
  • Run-length encoding: lossless data compression
• Cryptographic algorithms:
  • Symmetric (secret key) encryption:
    • AES
    • Blowfish
    • DES
    • IDEA
    • RC4
  • Asymmetric (public key) encryption or digital signature:
    • DSA
    • ElGamal
    • RSA
  • Message digest:
    • MD5
    • RIPEMD-160
    • SHA-1
  • Other:
    • Diffie-Hellman: key exchange
    • HMAC: keyed-hash message authentication
• Numerical algorithms:
  • Euclidean algorithm: computes the greatest common divisor
  • Exponentiating by squaring: quickly computes powers of numbers and matrices
  • Fast Fourier Transform: determines the frequencies contained in a (segment of a) signal
  • Gauss-Jordan elimination: solves systems of linear equations
  • Gauss-Legendre algorithm: computes the digits of pi
  • Gram-Schmidt Process: orthogonalizes a set of vectors
  • Integer factorization: breaking an integer into its prime factors
    • Lenstra Elliptic Curve Factorization
    • General Number Field Sieve
  • Multiplication algorithms: fast multiplication of two numbers
  • Primality tests: determining whether a given number is prime
    • Miller-Rabin primality test
    • Sieve of Eratosthenes: produces a list of the first primes
  • Newton's method: finds zeros of functions with calculus
  • Pseudorandom number generators: producing statistically random output
    • Blum Blum Shub: a pseudorandom number generator with a security proof
    • Yarrow algorithm
  • Rounding functions: the classic ways to round numbers
  • Square root: approximates the square root of a number
• Parsing:
  • CYK algorithm: decides whether a given string can be generated by a given context-free grammar
• Quantum algorithms:
  • Grover's algorithm: provides quadratic speedup for many search problems
  • Shor's algorithm: provides exponential speedup for factorizing a number
• Search algorithms:
  • Binary search: locates an item in a sorted vector
  • search tree">Binary search tree
  • Linear search: finds an item in an unsorted list
  • 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
  • search algorithm">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 a dictionary search.
  • String searching algorithms
• Sort algorithms:
  • search tree">Binary tree sort
  • Bogosort: humorous and slow
  • Bubble sort: for each pair of indices, swap the items if out of order
  • 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
  • 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 insertions sort
• Graph algorithms:
  • 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
  • Nonblocking Minimal Spanning Switch say, for a Telephone exchange
• Data visualization:
  • spring based algorithms
• Computer graphics:
  • Bresenham's line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points
  • Painter's algorithm: detects visible parts of a 3-dimensional scenery
  • Flood fill: fills a connected region of a multi-dimensional array with a specified symbol
• Other:
  • Subset-sum: Accepts the NP-complete language Subset-sum in polynomial time iff P=NP
  • Cyclic redundancy check: check word calculation
  • Halt: no one yet knows if this 43-byte C program ever halts
  • Parity: Is a number even or odd?
  • CHS_conversion: Converting between disk addressing systems
  • Xor swap algorithm: swaps the values of two variables without using a buffer