List of algorithms
From Wikinfo
The following is a list of the algorithms described in Wikipedia.
See also the list of 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.
- Compression algorithms:
- Arithmetic coding: advanced entropy coding
- Burrows-Wheeler transform: preprocessing useful for lossless compression
- DEFLATE: lossless data compression
- Delta encoding: aid to compression of data in which sequential data occurs oftenly
- Huffman coding: simple lossless entropy coding
- LZW: lossless data compression
- Run-length encoding: lossless data compression
- Cryptographic algorithms:
- Symmetric (secret key) encryption:
- Asymmetric (public key) encryption or digital signature:
- Message digest:
- Other:
- Diffie-Hellman: key exchange
- HMAC: keyed-hash message authentication
- 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:
- 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
- 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:
- Linear search: finds an item in an unsorted 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 a dictionary search.
- String searching algorithms
- Sort algorithms:
- 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:
- 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 test: 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
- 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
- Other:
- Subset-sum: Accepts the NP-complete language Subset-sum in polynomial time iff P=NP
- CORDIC: Conversion of rectangular coordinates to polar and vice versa
- Cyclic redundancy check: calculation of a check word
- 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
References
- Adapted from the Wikipedia article, "List_of_algorithms" http://en.wikipedia.org/wiki/List_of_algorithms, used under the GNU Free Documentation License
