Classics in Algorithmics

Mergesort

Herman H. Goldstine and John von Neumann, Planning and coding of problems for an electronic computing instrument, Part II, Volume 2. Reprinted in Design of Computers, Theory of Automata and Numerical Analysis, John von Neumann Collected Works V, Pergamon Press, Oxford (1963), 152--214

Matrix multiplication

Volker Strassen, Gaussian elimination is not optimal, Numerische Mathematik 13 (1969), 354--356

Closest pairs

Jon Louis Bentley and Michael Ian Shamos, Divide-and-conquer in multidimensional space, Proceedings of the 8th Annual ACM Symposium on Theory of Computing, ACM, New York (1976), 220--230

Randomized algorithms

Michael O. Rabin, Probabilistic algorithms, Algorithms and Complexity: New Directions and Recent Results (J. F. Traub, Ed.), Academic Press, New York (1976), 21--39

Partitioning

C. A. R. Hoare, Algorithm 63: PARTITION, Communications of the ACM 4 (1961), 321

Quicksort

C. A. R. Hoare, Algorithm 64: QUICKSORT, Communications of the ACM 4 (1961), 321

C. A. R. Hoare, Quicksort, The Computer Journal 5 (1962), 10--15

Selection

C. A. R. Hoare, Algorithm 65: FIND, Communications of the ACM 4 (1961), 321--322

Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences 7 (1973), 448--461

Minimum spanning trees

Joseph B. Kruskal, Jr., On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society 7 (1956), 48--50

R. C. Prim, Shortest connection networks and some generalizations, The Bell System Technical Journal 36 (1957), 1389--1401

Minimum-redundancy codes

David A. Huffman, A method for the construction of minimum-redundancy codes, Proceedings of the I.R.E. 40 (1952), 1098--1101

Disjoint sets

Robert Endre Tarjan, Efficiency of a good but not linear set union algorithm, Journal of the ACM 22 (1975), 215--225

Fourier transforms

James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation 19 (1965), 297--301

Multiplication

A. Karatsuba and Yu. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics --- Doklady 7 (1963), 595--596

A. Schönhage and V. Strassen, Schenelle Multiplikation großen Zahlen, Computing 7 (1971), 281--292

Arnold Schönhage, Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients, Proceedings of the European Computer Algebra Conference, Lecture Notes in Computer Science 144, Springer-Verlag, Berlin/Heidelberg (1982), 3--15

Search trees

G. M. Adel'son-Vel'skii and E. M. Landis, An algorithm for the organization of information, Soviet Mathematics --- Doklady 3 (1962), 1259--1263

R. Bayer and E. McCreight, Organization and maintenance of large ordered indexes, Acta Informatica 1 (1972), 173--189

Hash tables

J. Lawrence Carter and Mark N. Wegman, Universal classes of hash functions, Journal of Computer and System Sciences 18 (1979), 143--154

Michael L. Fredman, János Komlós, and Endre Szemerédi, Storing a sparse table with O(1) worst case access time, Journal of the ACM 31 (1984), 538--544

Amortized analysis

Robert Endre Tarjan, Amortized computational complexity, SIAM Journal on Algebraic and Discrete Methods 6 (1985), 306--318

Priority queues

J. W. J. Williams, Algorithm 232: HEAPSORT, Communications of the ACM 7 (1964), 347--348

Robert W. Floyd, Algorithm 245: TREESORT 3, Communications of the ACM 7 (1964), 701

Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM 21 (1978), 309--315

Michael L. Fredman and Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM 34 (1987), 596--615

Shortest paths

E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1 (1959), 269--271