List of algorithms: Difference between revisions

Revision as of 13:36, 8 January 2002

Revision as of 14:59, 8 January 2002

Line 7:

* [[Data compression|Compression algorithms]]:

* [[Binary search]]: locates an item in a sorted vector

** [[Run-length encoding]]: lossless data compression

* [[Binary search tree]]

** [[Huffman coding]]: simple lossless entropy coding

* [[Euclidean algorithm]]: computes the greatest common divisor of two numbers

** [[Data compression/Arithmetic coding|arithmetic coding]]: advanced entropy coding; encumbered by patents as of October 2001

* [[Exponentiating by squaring]]: quickly computes powers of numbers and matrices

** [[Data compression/LZW]] and [[Other LZ compression methods]]

* [[Fast Fourier Transform]]: determines the frequencies contained in a (segment of a) signal

** [[MP3]]: lossy audio compression

* [[Flood fill]]: Fills a connected region of a multi-dimensional array with a specified symbol

** [[JPEG]]: lossy image compression

* [[Grovers algorithm|Grover's algorithm]]: algorithm for a [[quantum computer]] giving quadratic speedup for many search problems

** [[Fractal Compression]]: lossy image compression

* [[Hash table algorithms]]

* Numerical algorithms:

* [[Linear search]]: finds an item in an unsorted list

** [[Euclidean algorithm]]: computes the [[greatest common divisor of two numbers]]

* [[PCX]]: (decompression algorithm)

** [[Exponentiating by squaring]]: quickly computes powers of numbers and matrices

* [[Perfect hashing]]

** [[ShorsSquare algorithm|Shor's algorithmroot]]: findsapproximates factorsthe square root of a number on a quantum computer

* [[Sortquantum algorithmcomputer|SortQuantum algorithms]]:

** [[Grovers algorithm|Grover's algorithm]]: algorithm for a [[quantum computer]] givingprovides quadratic speedup for many search problems

* [[Square root]]: approximates the square root of a number

** [[Shors algorithm|Shor's algorithm]]: provides exponential speedup for factorizing a number

* [[Search algorithm|Search algorithms]]:

** [[Binary search]]: locates an item in a sorted vector

** [[Binary search tree]]

** [[Linear search]]: finds an item in an unsorted list

* [[HashSort tablealgorithm|Sort algorithms]]:

** [[Binary search tree|Binary tree sort]]

** [[Bubble sort]]

** [[Heapsort]]

** [[Insertion sort]]

** [[Merge sort]]

** [[Pigeonhole sort]]

** [[Quicksort]]

** [[Radix sort]]

* [[Fast Fourier Transform]]: determines the frequencies contained in a (segment of a) signal

* [[Flood fill]]: Fills a connected region of a multi-dimensional array with a specified symbol

* [[Complexity_classes_P_and_NP|SUBSET-SUM]]: Solves an NP-complete problem in polynomial time iff P=NP