ALGORITHMS

Here are some algorithms we may consider for our final Top Ten:

  1. A* search algorithm
  2. AdaBoost (see Xindong Wu, "Top 10 algorithms in data mining", Knowledge and Informations Systems, Volume 14, Number 1, pages 1-37, January 2008)
  3. Algebraic eigenvalue solvers
  4. Ant colony optimization algorithms (see Marco Dorigo, Gianni Di Caro, Luca Gambardella, "Ant algorithms for discrete optimization", in "Artificial Life", MIT Press, 1999)
  5. Apportionment of congressional districts (see Brian Hayes, American Scientist, "Machine Politics", November-December 1996) (See Nick Berry, "Gerrymandering", March 2015).
  6. Approximate nearest neighbors for high dimensions (see David Mount, "ANN Programming Manual")
  7. Approximate string matching (see Gonzalo Navarro, "A Guided Tour to Approximate String Matching", ACM Computing Surveys, Volume 33, Number 1, pages 31-88, March 2001)
  8. the Approximate minimum degree algorithm (reduce nonzeros in Cholesky factor of a sparse symmetric matrix)
  9. Apriori algorithm (see Xindong Wu, "Top 10 algorithms in data mining", Knowledge and Informations Systems, Volume 14, Number 1, pages 1-37, January 2008)
  10. Aster, (reads a TeX file, including mathematical formulas, out loud for blind or visually impaired). (see Brian Hayes, American Scientist, "Speaking of Mathematics", March-April 1996)
  11. Auto-colorization of images
  12. Auto-Tune (see Sasha Frere Jones, "The Gerbil's Revenge", The New Yorker, 9 June 2008)
  13. Automatic essay scoring
  14. Automatic software verification
  15. B-Tree for decision process
  16. Babelfish, now Bing Translator
  17. Binary search
  18. Bitcoin
  19. The Black-Scholes equation
  20. Bloom filter (see Burton Bloom, "Space-time tradeoffs in Hash Coding with Allowable Errors", Communications of the ACM, Volume 13, Number 7, July 1970, pages 422-426)
  21. Blossom algorithm for maximum matching
  22. the Bootstrap algorithm
  23. Boruvka's parallel MST (minimum spanning tree) algorithm
  24. Byzantine fault tolerance (see Kevin Driscoll, Brendan Hall, Hakan Sivencrona, Phil Zumsteg, "Byzantine Fault Tolerance, from Theory to Reality")
  25. C4.5 classifier (see Xindong Wu, "Top 10 algorithms in data mining", Knowledge and Informations Systems, Volume 14, Number 1, pages 1-37, January 2008)
  26. the Caliper algorithm and convex hulls (see Nick Berry, "Bounding rectangles, convex hulls, bullet holes and video games", March 2014)
  27. Carry lookahead, an algorithm for anticipating carry bits in arithmetic (Koge-Stone adder, Brent-Kung adder)
  28. CART - Classification and Regression Trees (see Xindong Wu, "Top 10 algorithms in data mining", Knowledge and Informations Systems, Volume 14, Number 1, pages 1-37, January 2008)
  29. CESM, the Community Earth Simulation Model, (see Brian Hayes, "Clarity in Climate Modeling", American Scientist, November-December 2014)
  30. Chess playing programs, such as Deep Blue
  31. Compressive sensing
  32. Computer-Generated News articles - (see Steve Lohr, In case you wondered, a real human wrote this column, The New York Times, September 10, 2011.)
  33. Confidence Intervals from Sampled Data (see Nick Berry, "Confidence levels, sampling, marbles, and Greek urns", June 2014)
  34. Conjugate gradient method
  35. Credit card fraud detection
  36. CRUSH - Criminal Reduction Utilizing Statistical History
  37. Data compression (MP3) (see John MacCormick, "9 Algorithms that Changed the Future")
  38. Data stream algorithms (estimate min, max, most common, distinct elements in huge data stream) (see Brian Hayes, American Scientist, "The Britney Spears Problem", July-August 2008)
  39. Data stream random selection (select one item uniformly at random from a data stream of unknown length) (see Nick Berry, "Selecting a random person (fairly) from an unknown number of applicants", June 2013)
  40. Data stream unique count (estimate number of unique values in a data stream of unknown length) (see Nick Johnson, "Damn Cool Algorithms: Cardinality Estimation", blog.notdot.net )
  41. Database consistency (see John MacCormick, "9 Algorithms that Changed the Future")
  42. Datamining (see Nick Berry, "O! Say can you see...Datamining the White House Visitor book", January 2012)
  43. De Bruijn Sequences (see Nick Berry, "De Bruijn Sequences - What does DNA sequencing and guessing passwords have in common?", October 2013)
  44. Decision tree generation
  45. Decompositional approach to matrix computation (see G W Stewart, The Decompositional Approach to Matrix Computation, Computing in Science and Engineering, Volume 2, Number 1, January/February 2000, pages 50-59.)
  46. Deep learning (see Brian Hayes, "Delving into Deep Learning", American Scientist, May-June 2014).
  47. Depixelization of images (see Nick Berry, "Pixel scalars. How to rescale bitmap images", December 2013)
  48. Diffie-Hellman key exchange algorithm
  49. Digital signatures (see John MacCormick, "9 Algorithms that Changed the Future")
  50. Dijkstra's shortest path algorithm
  51. Discrete Cosine Transform (see Nick Berry, "Discrete Cosine Transforms - How JPG's work, and fun secret images", November 2012)
  52. Distributed hash tables
  53. Document analysis (did the same person write all these articles?)
  54. Doomsday algorithm for the day of the week given a date (Conway)
  55. Driverless vehicles, automatic navigation, Mcity test environment (see Brian Hayes, American Scientist, "Leave the Driving to It", September-October 2011)
  56. eBooks and electronic publishing
  57. EM, expectation maximization algorithm (see Xindong Wu, "Top 10 algorithms in data mining", Knowledge and Informations Systems, Volume 14, Number 1, pages 1-37, January 2008)
  58. Error correcting codes (see John MacCormick, "9 Algorithms that Changed the Future") (see A K Dewdney, "The Turing Omnibus: Error correcting codes")
  59. Error detecting codes: parity bit, ISBN check digit, Luhn checksum
  60. Exponentiation by halving
  61. Facebook news feed
  62. Facial recognition
  63. Fast Fourier transform (see Daniel Rockmore, The FFT: An Algorithm the Whole Family Can Use, Computing in Science and Engineering, Volume 2, Number 1, January/February 2000, pages 60-64.) (see A K Dewdney, "The Turing Omnibus: Fast Fourier Transform")
  64. Fast multipole method (see John Board, Klaus Schulten, The Fast Multipole Algorithm, Computing in Science and Engineering, Volume 2, Number 1, January/February 2000, pages 76-79.)
  65. Finite difference methods for wave problems
  66. Finite element method
  67. Floyd-Warshall algorithm
  68. Fortran compiler (see David Padua, The Fortran I Compiler, Computing in Science and Engineering, Volume 2, Number 1, January/February 2000, pages 70-75.)
  69. Fourier transform (see Brian Hayes, American Scientist, "Life Cycles", July-August 2005)
  70. Fuzzy logic
  71. Genetic algorithms (see Nick Berry, "A practical use for Genetic Programming", April 2009)
  72. GMRES, generalized minimum residual for sparse linear systems
  73. Google AdWords
  74. Google Search (it finds things for you) (it learns from your choices)
  75. Google Translate (photograph a sign in a foreign language, get a translation)
  76. GPS, Global Positioning System (see "How GPS Receivers Work", http://electronics.howstuffworks.com/gadgets/travel/gps.htm )
  77. GPU parallel algorithms
  78. the Gram-Schmidt algorithm for orthogonal basis
  79. Graph algorithms (see Brian Hayes, American Scientist, "Graph Theory in Practice: Part I and II", January-February 2000, March-April 2000.
  80. The Gray Code (see Nick Berry, "Gray Coded Binary", November 2014)
  81. Hash algorithms (see A K Dewdney, "The Turing Omnibus: Storage by Hashing")
  82. Heap sort (see A K Dewdney, "The Turing Omnibus: Heaps and Merges")
  83. Heuristic algorithms for NP-complete problems
  84. Hidden Markov models
  85. High frequency stock trading
  86. Hilbert Curve Point Indexing (see Nick Johnson, "Damn Cool Algorithms: Spatial indexing with Quadtrees and Hilbert Curves", 09 November 2009, blog.notdot.net ) (See Nick Berry, "Hilbert Curves", March 2013) (see Brian Hayes, "Crinkly Curves", May-June 2013)
  87. Hill climbing for optimization
  88. The Hubbard model of magnetization, conduction, superconductivity (see Brian Hayes, American Scientist, "Hip-Hop Physics", November-December 2009)
  89. Huffman compression (see A K Dewdney, "The Turing Omnibus: Text Compression")
  90. Inductive inference in machine learning
  91. Integer factorization
  92. Integer relation detection (see David Bailey, "Integer Relation Detection", Computing in Science and Engineering, Volume 2, Number 1, January/February 2000, pages 24-28)
  93. The Ising model of magnetization (see Brian Hayes, American Scientist, "The World in a Spin", September-October 2000)
  94. Iterative linear algebraic solvers
  95. K-means (see Xindong Wu, "Top 10 algorithms in data mining", Knowledge and Informations Systems, Volume 14, Number 1, pages 1-37, January 2008)
  96. kNN - K nearest neighbors (see Xindong Wu, "Top 10 algorithms in data mining", Knowledge and Informations Systems, Volume 14, Number 1, pages 1-37, January 2008)
  97. Krylov subspace iteration (see Henk van der Vorst, Krylov Subspace Iteration, Computing in Science and Engineering, Volume 2, Number 1, January/February 2000, pages 32-37.)
  98. Lanczos eigenvalue method
  99. Linear sketching (compressed sensing, data streams) (see Andrew McGregor slides)
  100. Link analysis for graphs
  101. the Luhn check-digit algorithm
  102. LZ (Lempel-Ziv) compression
  103. Map reduce (see Jeffrey Dean, Sanjay Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters", research.google.com/archive/mapreduce.html )
  104. Markov Chain Monte Carlo (see Nick Berry, "Markov Chains, Monte-Carlo, and Chutes and Ladders", November 2011)
  105. Matrix decomposition approach
  106. McCready algorithm to predict hit records (see "Chris Steiner, "Automate This: How Algorithms Came To Rule Our World")
  107. MD5, the Message Digest (a hash function that is still widely used to provide digital signatures, although it has been known to be vulnerable to attack for 10 years) (see Bruce Schneier, "Cryptanalysis of MD5 and SHA: Time for a New Standard", Computerworld, August 19, 2004, https://www.schneier.com/essays/archives/2004/08/cryptanalysis_of_md5.html )
  108. Merge sort (see A K Dewdney, "The Turing Omnibus: Heaps and Merges")
  109. Metropolis Monte Carlo Algorithm (see Isabel Beichl, Francis Sullivan, The Metropolis Algorithm, Computing in Science and Engineering, Volume 2, Number 1, January/February 2000, pages 65-69.)
  110. Minimal spanning trees (see A K Dewdney, "The Turing Omnibus: Minimum Spanning Trees")
  111. Models of national economies
  112. Monte Carlo method (see A K Dewdney, "The Turing Omnibus: Simulation")
  113. MPI, a framework for parallel programming
  114. Multigrid method for linear equations
  115. Multiple precision arithmetic (David Bailey's MPFUN2015 package)
  116. N-body problems (see Brian Hayes, "The 100-Billion-Body Problem", American Scientist, March-April 2015, "A Box of Universe", American Scientist, January-February 2012)
  117. Naive Bayes (see Xindong Wu, "Top 10 algorithms in data mining", Knowledge and Informations Systems, Volume 14, Number 1, pages 1-37, January 2008)
  118. Nearest neighbors classifier
  119. Neural networks (see A K Dewdney, "The Turing Omnibus: Neural Nets")
  120. Noisy Signal Analysis (see Nick Berry, "Detecting targets in noisy radar signals", May 2014)
  121. Nonlinear algebraic solvers
  122. Nonlinear programming
  123. NSA Data Collection (see Brian Hayes, American Scientist, "Connecting the Dots", September-October 2006)
  124. OKCupid date matching
  125. OpenMP - a parallel programming environment
  126. PageRank - how Google ranks web pages (see Xindong Wu, "Top 10 algorithms in data mining", Knowledge and Informations Systems, Volume 14, Number 1, pages 1-37, January 2008) (see John MacCormick, "9 Algorithms that Changed the Future") (see Cleve Moler, "Experiments in Matlab: Chapter 7, Google PageRank", https://www.mathworks.com/moler/exm/chapters/pagerank.pdf ) (see David Gleich, "PageRank Beyond the Web", SIAM Review, Volume 57, Number 3, 2015, pages 321-363.)
  127. Pancake sorting - sort a list of numbers, but only by reversing any initial sublist (see Brian Hayes, American Scientist, "Sorting out the genome", September-October 2007). (See GRIMM program, grimm.ucsd.edu/GRIMM/ )
  128. Pattern recognition (see John MacCormick, "9 Algorithms that Changed the Future")
  129. the Perceptron (see A K Dewdney, "The Turing Omnibus: Perceptrons")
  130. the Power Method for a Dominant Eigenvector (works with messy data, can be applied to a directed graph such as the web, works well with sparse data, result of one step can be computed incrementally or with distributed memory)
  131. Proportional integral derivative algorithm
  132. Proportional navigation (see Nick Berry, "How modern missile guidance systems work", August 2014)
  133. Protein structure prediction (the folding problem) (see Brian Hayes, American Scientist, "Prototeins", May-June 1998) (see Ken Dill, Justin MacCallum, "The Protein-Folding Problem, 50 Years On", Science, Volume 338, 23 November 2012, pages 1042-1047)
  134. Public key cryptography (see A K Dewdney, "The Turing Omnibus: Public Key Cryptography")
  135. QR ("Quick Response") codes - (see Nick Berry, "QR codes - How do they work, and how much can you damage them and still have them work?", November 2013) (see http://science.howstuffworks.com/innovation/repurposed-inventions/2d-barcodes.htm )
  136. QR eigenvalue algorithm (see Beresford Parlett, The QR Algorithm, Computing in Science and Engineering, Volume 2, Number 1, January/February 2000, pages 38-42.)
  137. Quadtrees (see A K Dewdney, "The Turing Omnibus: Storing Images")
  138. Quasi-random number generation (see Brian Hayes, American Scientist, "Quasirandom Ramblings", July-August 2011)
  139. Quick sort (see Joseph Jaja, A Perspective on Quicksort, Computing in Science and Engineering, Volume 2, Number 1, January/February 2000, pages 43-49.)
  140. Random number generation (see Brian Hayes, American Scientist, "The Wheel of Fortune", March-April 1993) (see A K Dewdney, "The Turing Omnibus: Random Numbers")
  141. Recommendation systems, "You May Also Enjoy", NetFlix, Amazon
  142. Relational databases
  143. the Remez exchange algorithm (find simple uniform approximations to functions)
  144. Ripple carry adder, an algorithm for handling the carry bits in addition
  145. Routing algorithms - (Google Map)
  146. RSA public key encryption (see Brian Hayes, "The Magic Words are Squeamish Ossifrage", July-August 1994) (see John MacCormick, "9 Algorithms that Changed the Future")
  147. Sabre (Semi-Automatic Business Research Environment) (Airline reservations) (see Sara Robinson, "Computer Scientists Find Unexpected Depths in Airfare Search Problem", SIAM News, Volume 5, Number 6, July/August 2002)
  148. Search engine indexing (see John MacCormick, "9 Algorithms that Changed the Future")
  149. Search trees (see A K Dewdney, "The Turing Omnibus: Search Trees")
  150. Secure Hash Algorithm, (SHA-0, SHA-1, SHA-2, SHA-3)
  151. Shamir's password algorithm (see Nick Berry, "How to share secrets securely (without breaking plates)", November 2012)
  152. Shazam song recognition
  153. Shor's quantum algorithm
  154. Shuffling algorithms (see Nick Berry, "Good and bad shuffling algorithms", November 2014)
  155. Simplex method for linear programming (see John Nash, The (Dantzig) Simplex Method for Linear Programming, Computing in Science and Engineering, Volume 2, Number 1, January/February 2000, pages 29-31.) (see A K Dewdney, "The Turing Omnibus: Linear programming")
  156. Simulated annealing
  157. Single linkage clustering
  158. Soundex
  159. Spam detection (see Brian Hayes, American Scientist, "Spam, Spam, Spam, Lovely Spam", May-June 2003.)
  160. Spelling checker
  161. SQL
  162. Stable marriage algorithm, basis for National Resident Matching Program (see Alvin Roth, Elliott Peranson, Design of the matching market for American physicians: the engineering aspects of economic design, The American Economic Review, Volume 89, Number 4, pages 748-780, September 1999.)
  163. String searching - find a word or phrase rapidly (see A K Dewdney, "The Turing Omnibus: Searching Strings")
  164. Subset sum (see A K Dewdney, "The Turing Omnibus: The Partition Problem")
  165. Subset sum encryption (see Brian Hayes, American Scientist, "The Easiest Hard Problem", March-April 2002)
  166. Support vector machines (see Xindong Wu, "Top 10 algorithms in data mining", Knowledge and Informations Systems, Volume 14, Number 1, pages 1-37, January 2008)
  167. Traffic simulation (see Brian Hayes, "Playing in Traffic", American Scientist, July-August 2015)
  168. Tree algorithms for biology
  169. Triangulation using the Delaunay method
  170. the Trust Region algorithm for optimization
  171. UPC, the Universal Price Code (see http://electronics.howstuffworks.com/gadgets/high-tech-gadgets/upc.htm )
  172. Voice recognition
  173. Watson, IBM's program for playing Jeopardy using clever web searches has developed into an entire operating system for artificial intelligence handling of big data, called "cognitive computing";
  174. Wavelets
  175. Whole cell simulation, (Harold Morowitz, Markus Covert) (see Brian Hayes, "Imitation of Life", American Scientist, January-February 2013)
  176. Zero knowledge protocols (see Matthew Green, http://blog.cryptographyengineering.com/2014/11/zero-knowledge-proofs-illustrated-primer.html)

Last revised on 27 September 2015.