References
Here is a list of references, including many seminal papers and advanced resources.
Please note that links to the copyrighted papers are not accessible from this site.
1. FUNDAMENTALS
 Writing correct programs
by J. Bentley.
Communications of the ACM, Vol. 26, No. 12, pp. 10401045 (December 1983).
Even binary search is hard to program correctly.  Big Omicron and big Omega and big Theta
by D. Knuth.
SIGACT News, 1976.
A note on bigOh and related notations.  On a class of O(n^2) problems in
computational geometry
by A. Gajentaan and M. H. Overmars.
Computational Geometry, Vol. 5, pp. 165185 (1995).
3SUMhard problems. 
Set merging algorithms
by J. E. Hopcroft and J. D. Ullman.
SIAM Journal on Computing, Vol. 2, No. 4, 294303 (April 1973).
Iterated log analysis of weighted quick union with path compression. 
Efficiency of a good but not linear set union algorithm
by R. E. Tarjan.
Journal of the ACM, Vol. 22, No. 2, 215225 (April 1975).
Inverse Ackermann analysis of weighted quick union with path compression. 
The cell probe complexity of dynamic data structures
by M. L. Fredman and M. E. Saks.
In Proceeding of STOC 1989, pp. 345354.
Ackermann lower bound for unionfind.
2. SORTING

A highspeed sorting procedure
by D. L. Shell.
Communications of the ACM, Vol. 2, No. 7 (July 1959).
Shellsort algorithm. 
Analysis of Shellsort and related algorithms
by R. Sedgewick.
Proceedings of ESA 1996, pp. 2527.
Survey of the analysis of Shellsort. 
Optimal stable merging
by A. Symvonis.
The Computer Journal, Vol. 38, No. 8 (1995).
Inplace and stable mergesort. 
Quicksort
by C. A. R. Hoare.
The Computer Journal, Vol. 5, No. 1, pp. 1016 (1962).
Quicksort algorithm. 
Implementing quicksort programs
by R. Sedgewick.
Communications of the ACM, Vol. 21, No. 10, pp. 847857 (October 1978).
Practical study of how to implement quicksort. 
The analysis of quicksort programs
by R. Sedgewick.
Act Informatica, Vol. 7, pp. 327355 (1977).
Theoretical analysis of quicksort variants. 
Engineering a system sort
by J. L. Bentley and M. D. McIlroy.
Software: Practice and Experience, Vol. 23, No. 11, pp. 12491265 (November 1993).
BentleyMcIlroy 3way partioning algorithm.  A killer adversary for quicksort.
M. D. McIlroy.
Software: Practice and Experience, Vol. 29, No. 4, pp. 14 (April 1999).
Worstcase inputs for deterministic quicksorts.  Three beautiful quicksorts.
J. L. Bentley.
Googl Tech Talks, August 9, 2007.
Three implementations of quicksort along with historic context. 
Average case analysis
of Java 7's dual pivot quicksort.
S. Wild and M. E. Nebel.
In Proceedings of the 20th European Symposium on Algorithms, 2012.
Analysis of Yaroslavskiy's dualpivot quicksort used in Java 7. 
An analysis of algorithms
for the Dutch national flag problem by C. L. McMaster.
Communications of the ACM, Vol. 21, No. 10, pp. 842847 (October 1978).
Various 3way partitioning algorithms.  Algorithm 232: Heapsort by J. W. J. Williams.
Communications of the ACM, Vol. 7, No. 6, pp. 347348 (June 1964).
Heapsort algorithm. 
Algorithm 245: Treesort by R. W. Floyd.
Communications of the ACM, Vol. 7, No. 12, p. 701 (December 1964).
Floyd's variant of heapsort. 
The analysis of heapsort by R. Schaffer and R. Sedgewick.
Journal of Algorithms, Vol. 15, No, 1, pp. 76100 (July 1993).
Linearithmic best and average case analysis of heapsort.  Time bounds for selection
by M. Blum, R. W. Floyd, V. R. Pratt, R. L. Rivest, and R. E. Tarjan.
Journal of Computer and System Sciences,
Vol. 7, No. 4, pp. 448461 (August 1973).
Expected lineartime selection algorithm. 
Samplesort: a sampling approach to minimal storage tree sorting
by W. D. Frazer and A. C. McKellar.
Journal of the ACM, Vol. 17, No. 3, pp. 496507 (July 1970).
Samplesort algorithm. 
An efficient algorithm for determining the convex hull of a finite point set
by R. L. Graham.
Information Processing Letters, Vol. 1, pp. 132133 (1972).
Graham scan algorithm for convex hull. 
A lower bound for finding convex hulls by A. C. Yao.
Journal of the ACM, Vol. 28, No. 4, pp. 780787 (October 1981).
Linearithmic lower bound for convex hull in quadratic decision tree model. 
Lower bounds for algebraic computation trees
by M. BenOr.
In Proceeding of STOC 1983, pp. 8086.
Linearithmic lower bounds for sorting and related problems in algebraic decision tree model.
3. SEARCHING

A dichromatic framework for balanced trees by
L. J. Guibas and R. Sedgewick.
In Proceedings of FOCS 1978, pp. 821.
Redblack BSTs.  Randomized binary search trees
by C. Martinez and S. Roura.
Journal of the ACM, Vol. 45, No. 2, pp. 288323 (March 1998).
Randomized BSTs.  Selfadjusting binary search trees
by D. D. Sleator and R. E. Tarjan.
Journal of the ACM, Vol. 32, No. 3, pp. 652686 (July 1985).
Splay trees. 
How tall is a tree by B. Reed.
In proceeding of STOC 2000, pp. 479483.
Asymptotics of height of a randomized BST. 
Analysis of the standard deletion algorithms in
exact fit domain binary search trees
by J. Culberson and J. I. Munro.
Algorithmica, Vol. 5, pp. 295311 (1990).
sqrt(n) analysis for BST with Hibbard deletions. 
Exact distribution of individual displacements in linear probing hashing
by A. Viola.
ACM Transactions on Algorithms, Vol. 1, No. 2, pp. 214242 (October 2005).
Analysis of Knuth's parking problem.  Multidimensional binary
search trees used for associative searching by J. L. Bentley.
Communications of the ACM, Vol. 18, No. 9, pp. 509517 (September 1975).
Kdtree data structure.
4. GRAPHS

Depthfirst search and linear graph algorithms
by R. E. Tarjan.
SIAM Journal of Computing, Vol. 1, No. 2, pp. 146160 (June 1972).
Lineartime algorithms for strong components and biconnected components. 
Finding dominators in directed graphs
by R. E. Tarjan.
SIAM Journal of Computing, Vol. 3, No. 1, pp. 6289 (March 1974).
DFSbased topological sorting. 
A strongconnectivity algorithm and its
applications in data flow analysis by M. Sharir.
Computers and Mathematics with Applications, Vol. 7, pp. 6772 (1981).
Kosaraju's strong components algorithm. 
A lineartime algorithm for testing the truth of certain quantified
boolean formulas by B. Aspvall, M. F. Plass, and R. E. Tarjan.
Information Processing Letters, Vol. 8, No. 3, pp. 121123 (1979).
Lineartime algorithm for 2SAT using strong components. 
On a certain minimal problem by O. Boruvka.
Boruvka's MST algorithm. 
A note on two problems in connexion with graphs by E. W. Dijkstra.
Numerische Mathematik, Vol. 1, pp. 269271 (1959).
Dijkstra's shortest paths algorithm. 
Shortest connection networks and some generalizations by R. C. Prim.
Bell System Technology Journal, Vol. 36, pp. 13891401 (1957).
Prim's MST algorithm. 
On the shortest spanning subtree of a graph and the traveling salesman problem
by J. B. Kruskal, Jr.
Proceedings of the American Mathematical Society, Vol. 7, No. 1, pp. 4850 (February 1956).
Kruskal's MST algorithm.  On a routing problem by R. Bellman.
Quarterly of Applied Mathematics, Vol. 16, pp. 8790 (1958).
BellmanFord shortest paths algorithm.  Network flow theory by L. R. Ford, Jr.
Technical Report P923, The Rand Corporation (August 1956).
BellmanFord shortest paths algorithm. 
Negativecycle detection algorithms
by B. V. Cherkassky and A. V. Goldberg.
Mathematical Programming, Vol. 85, pp. 349363 (1996).
A survey of negativecycle detection algorithms. 
On the history of the minimum spanning tree problem
by R. L. Graham and P. Hell.
Annals of the History of Computing, Vol. 7, No. 1, pp. 4357 (January 1985).
An authoritative history of the MST problem. 
On the history of combinatorial optimization (till 1960)
by A. Schrijver.
Handbook in Operations Research and Management Science, Vol. 12, pp. 168 (2005).
An authoritative history of several combinatorial optimization problems.
5. STRINGS
 Engineering Radix Sorts by
P. M. McIlroy, K. Bostic, and M. D. McIlroy.
Computing Systems, Vol. 6, No. 1, pp. 527 (Winter 1993).
Implementations of MSD radix sort.  DataSpecific Analysis of String Sorting by
R. Seidel.
SODA 2010.
Analysis of string sorting algorithms in the random string model.  Fast pattern matching in strings by
D. E. Knuth, J. H. Morris, and V. R. Pratt.
SIAM Journal on Computing, Vol. 6, No. 2, pp. 323350 (June 1977).
KnuthMorrisPratt substring search algorithm.  A fast string searching algorithm
by R. S. Boyer and J. S. Boore.
Communications of the ACM, Vol. 20, No. 10, pp. 762772 (October 1977).
BoyerMoore substring search algorithm.  Practical fast searching in strings
by R. N. Horspool.
Software: Practice and Experience, VOl. 10, pp. 501506 (1980).
Simpler variant of BoyerMoore.  Efficient randomized patternmatching algorithms
by R. M. Karp and M. O. Rabin.
IBM Journal of Research and Development, Vol. 31, No. 2, pp. 249260 (March 1987).
KarpRabin fingerprint string search.  Fast algorithms for sorting and searching strings
by J. L. Bentley and R. Sedgewick.
In Proceedings of SODA 1997.
3way radix sort and ternary search tries. 
A universal algorithm for sequential data compression
by J. Ziv and A. Lempel.
IEEE Transactions on Information Theory, Vol. 23, No. 3, pp. 337343 (May 1977).
LZ77 data compression. 
Compression of individual sequences via variablerate coding
by J. Ziv and A. Lempel.
IEEE Transactions on Information Theory, Vol. 24, No. 5, pp. 530536 (September 1978).
LZ78 data compression. 
A method for the construction of minimumredundancy codes
by D. Huffman.
Institute of Radio Engineers, Vol. 40, No. 9, pp. 10981101 (September 1952).
Huffman data compression. 
A blocksorting lossless data compression algorithm
by M. Burrows and D. J. Wheeler.
Technical report 124, Digital Equipment Corporation (May 1994).
BurrowsWheeler data compression. 
A locally adaptive data compression scheme
by J.L. Bentley, D. D. Sleator, R. E. Tarjan, and V. K. Wei.
Communications of the ACM, Vol. 29, No. 4, pp. 320330 (April 1986).
Movetofront coding. 
PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric
by D. R. Morrison.
Journal of the ACM, Vol. 15, No. 4, pp. 514534 (October 1968).
Patricia tries.
6. CONTEXT

Organization and maintenance
of large ordered indexes
R. Bayer and E. McCreight.
Acta Informatica, Vol. 1, No. 3, pp. 173189 (1972).
Btree data structure. 
Maximal flow through a network
L. R. Ford, Jr. and D. R. Fulkerson.
Canadian Journal of Mathematics, pp. 399404 (1956).
FordFulkerson algorithm for the maxflow problem. 
A note on the maximum flow
through a network by P. Elias, A. Feinstein, and C. E. Shannon.
IRE Transactions on Information Theory, Vol. 2, No. 4, pp. 117119 (December 1956).
A proof of the maxflow mincut theorem, independent, but subsequent to FordFulkerson. 
Theoretical improvements in algorithmic
efficiency for network flow problems by
J. Edmonds and R. M. Karp.
Journal of the ACM, Vol. 19, No. 2, pp. 258264 (1972).
The shortest and highest capacity augmenting path heuristics for the FordFulkerson algorithm. 
On implementing pushrelabel method
for the maximum flow problem by Boris V. Cherkassky and Andrew V. Goldberg.
Integer Programming and Combinatorial Optimization, Vol. 920, pp. 157171 (1995).
Efficient implementations of the pushrelabel method for the maximum flow problem. 
Computational investigations of maximum
flow algorithms by Ravindra K. Ahuja, Murali Kodialam, Ajay K. Mishra,
and James B. Orlin.
European Journal of Operations Research, Vol. 97, pp. 509542 (1997).
Comparison of several maximum flow algorithms in practice. 
Efficient Maximum Flow Algorithms
A. V. Goldberg and R. E. Tarjan.
Communications of the ACM, pp. 8289 (2014).
Overview of efficient algorithms for the maxflow problem. 
Network flow algorithms by A. V. Goldberg, E. Tardos, and R. E. Tarjan.
In Algorithms and Combinatorics edited by B. Korte, L. Lovasz, H. J. Promel, and
A. Schrijver.
Survey of network flow algorithm. 
Notes on suffix sorting
by N. J. Larsson.
Tech report LUCDTR:98204, Lund University.
Linearithmic analysis of Sadakane's suffix sorting algorithm. 
Simple linear work suffix array construction
by J. Karkkainen and P. Sanders.
Suffix sorting in linear time. 
Paths, trees, and flowers by J. Edmonds.
Canadian Journal of Mathematics, Vol. 17, pp. 449467 (February 1965).
Association of polynomialtime algorithm with efficient algorithm.  The complexity of theorem proving
by S. A. Cook.
In Proceedings of STOC 1971, pp. 151158.
Satisfiability is NPcomplete.  Reducibility among
combinatorial problems by R. M. Karp.
In Complexity of Computer Computations, pp. 85103.
21 diverse combinatorial problems are NPcomplete.