- 1
-
Free eBooks by Project Gutenberg.
Available from: http://www.gutenberg.org/ [cited 2011-10-12].
- 2
-
IEEE Standard for Floating-Point Arithmetic.
Technical report, Microprocessor Standards Committee of the IEEE
Computer Society, 3 Park Avenue, New York, NY 10016-5997, USA, August 2008.
http://dx.doi.org/10.1109/IEEESTD.2008.4610935
doi:10.1109/IEEESTD.2008.4610935.
- 3
-
G.M. Adelson-Velskii and E.M. Landis.
An algorithm for the organization of information.
Soviet Mathematics Doklady, 3(1259-1262):4, 1962.
- 4
-
A. Aggarwal and J. S. Vitter.
The input/output complexity of sorting and related problems.
Communications of the ACM, 31(9):1116-1127, 1988.
- 5
-
A. Andersson.
Improving partial rebuilding by using simple balance criteria.
In F. K. H. A. Dehne, J.-R. Sack, and N. Santoro, editors, Algorithms and Data Structures, Workshop WADS '89, Ottawa, Canada, August
17-19, 1989, Proceedings, volume 382 of Lecture Notes in Computer
Science, pages 393-402. Springer, 1989.
- 6
-
A. Andersson.
Balanced search trees made simple.
In F. K. H. A. Dehne, J.-R. Sack, N. Santoro, and S. Whitesides,
editors, Algorithms and Data Structures, Third Workshop, WADS '93,
Montréal, Canada, August 11-13, 1993, Proceedings, volume 709 of Lecture Notes in Computer Science, pages 60-71. Springer, 1993.
- 7
-
A. Andersson.
General balanced trees.
Journal of Algorithms, 30(1):1-18, 1999.
- 8
-
A. Bagchi, A. L. Buchsbaum, and M. T. Goodrich.
Biased skip lists.
In P. Bose and P. Morin, editors, Algorithms and Computation,
13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November
21-23, 2002, Proceedings, volume 2518 of Lecture Notes in Computer
Science, pages 1-13. Springer, 2002.
- 9
-
R. Bayer and E. M. McCreight.
Organization and maintenance of large ordered indexes.
In SIGFIDET Workshop, pages 107-141. ACM, 1970.
- 10
-
Bibliography on hashing.
Available from:
http://liinwww.ira.uka.de/bibliography/Theory/hash.html [cited
2011-07-20].
- 11
-
J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway.
UMAC: Fast and secure message authentication.
In M. J. Wiener, editor, Advances in Cryptology - CRYPTO '99,
19th Annual International Cryptology Conference, Santa Barbara, California,
USA, August 15-19, 1999, Proceedings, volume 1666 of Lecture Notes in
Computer Science, pages 79-79. Springer, 1999.
- 12
-
P. Bose, K. Douïeb, and S. Langerman.
Dynamic optimality for skip lists and b-trees.
In S.-H. Teng, editor, Proceedings of the Nineteenth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco,
California, USA, January 20-22, 2008, pages 1106-1114. SIAM, 2008.
- 13
-
A. Brodnik, S. Carlsson, E. D. Demaine, J. I. Munro, and R. Sedgewick.
Resizable arrays in optimal time and space.
In Dehne et al. [18], pages 37-48.
- 14
-
J.L. Carter and M.N. Wegman.
Universal classes of hash functions.
Journal of computer and system sciences, 18(2):143-154, 1979.
- 15
-
D. Comer.
The ubiquitous B-tree.
ACM Computing Surveys, 11(2):121-137, 1979.
- 16
-
C.A. Crane.
Linear lists and priority queues as balanced binary trees.
Technical Report STAN-CS-72-259, Computer Science Department,
Stanford University, 1972.
- 17
-
S.A. Crosby and D.S. Wallach.
Denial of service via algorithmic complexity attacks.
In Proceedings of the 12th USENIX Security Symposium, pages
29-44, 2003.
- 18
-
F. K. H. A. Dehne, A. Gupta, J.-R. Sack, and R. Tamassia, editors.
Algorithms and Data Structures, 6th International Workshop, WADS
'99, Vancouver, British Columbia, Canada, August 11-14, 1999, Proceedings,
volume 1663 of Lecture Notes in Computer Science. Springer, 1999.
- 19
-
L. Devroye.
Applications of the theory of records in the study of random trees.
Acta Informatica, 26(1):123-130, 1988.
- 20
-
P. Dietz and J. Zhang.
Lower bounds for monotonic list labeling.
In J. R. Gilbert and R. G. Karlsson, editors, SWAT 90, 2nd
Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 11-14, 1990,
Proceedings, volume 447 of Lecture Notes in Computer Science, pages
173-180. Springer, 1990.
- 21
-
M. Dietzfelbinger.
Universal hashing and -wise independent random variables via
integer arithmetic without primes.
In C. Puech and R. Reischuk, editors, STACS 96, 13th Annual
Symposium on Theoretical Aspects of Computer Science, Grenoble, France,
February 22-24, 1996, Proceedings, volume 1046 of Lecture Notes in
Computer Science, pages 567-580. Springer, 1996.
- 22
-
M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger.
Polynomial hash functions are reliable.
In W. Kuich, editor, Automata, Languages and Programming, 19th
International Colloquium, ICALP92, Vienna, Austria, July 13-17, 1992,
Proceedings, volume 623 of Lecture Notes in Computer Science, pages
235-246. Springer, 1992.
- 23
-
M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen.
A reliable randomized algorithm for the closest-pair problem.
Journal of Algorithms, 25(1):19-51, 1997.
- 24
-
M. Dietzfelbinger, A. R. Karlin, K. Mehlhorn, F. Meyer auf der Heide,
H. Rohnert, and R. E. Tarjan.
Dynamic perfect hashing: Upper and lower bounds.
SIAM Journal on Computing, 23(4):738-761, 1994.
- 25
-
A. Elmasry.
Pairing heaps with
decrease cost.
In Proceedings of the twentieth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 471-476. Society for Industrial and Applied
Mathematics, 2009.
- 26
-
F. Ergun, S. C. Sahinalp, J. Sharp, and R. Sinha.
Biased dictionaries with fast insert/deletes.
In Proceedings of the thirty-third annual ACM symposium on
Theory of computing, pages 483-491, New York, NY, USA, 2001. ACM.
- 27
-
M. Eytzinger.
Thesaurus principum hac aetate in Europa viventium (Cologne).
1590.
In commentaries, `Eytzinger' may appear in variant forms, including:
Aitsingeri, Aitsingero, Aitsingerum, Eyzingern.
- 28
-
R. W. Floyd.
Algorithm 245: Treesort 3.
Communications of the ACM, 7(12):701, 1964.
- 29
-
M. L. Fredman, J. Komlós, and E. Szemerédi.
Storing a sparse table with 0 (1) worst case access time.
Journal of the ACM, 31(3):538-544, 1984.
- 30
-
M. L. Fredman and D. E. Willard.
Surpassing the information theoretic bound with fusion trees.
Journal of computer and system sciences, 47(3):424-436, 1993.
- 31
-
M.L. Fredman, R. Sedgewick, D.D. Sleator, and R.E. Tarjan.
The pairing heap: A new form of self-adjusting heap.
Algorithmica, 1(1):111-129, 1986.
- 32
-
M.L. Fredman and R.E. Tarjan.
Fibonacci heaps and their uses in improved network optimization
algorithms.
Journal of the ACM, 34(3):596-615, 1987.
- 33
-
I. Galperin and R.L. Rivest.
Scapegoat trees.
In Proceedings of the fourth annual ACM-SIAM Symposium on
Discrete algorithms, pages 165-174. Society for Industrial and Applied
Mathematics, 1993.
- 34
-
A. Gambin and A. Malinowski.
Randomized meldable priority queues.
In SOFSEM’98: Theory and Practice of Informatics, pages
344-349. Springer, 1998.
- 35
-
M. T. Goodrich and J. G. Kloss.
Tiered vectors: Efficient dynamic arrays for rank-based sequences.
In Dehne et al. [18], pages 205-216.
- 36
-
Goetz Graefe.
Modern b-tree techniques.
Foundations and Trends in Databases, 3(4):203-402, 2010.
- 37
-
R. L. Graham, D. E. Knuth, and O. Patashnik.
Concrete Mathematics.
Addison-Wesley, 2nd edition, 1994.
- 38
-
L.J. Guibas and R. Sedgewick.
A dichromatic framework for balanced trees.
In 19th Annual Symposium on Foundations of Computer Science, Ann
Arbor, Michigan, 16-18 October 1978, Proceedings, pages 8-21. IEEE
Computer Society, 1978.
- 39
-
C. A. R. Hoare.
Algorithm 64: Quicksort.
Communications of the ACM, 4(7):321, 1961.
- 40
-
J. E. Hopcroft and R. E. Tarjan.
Algorithm 447: Efficient algorithms for graph manipulation.
Communications of the ACM, 16(6):372-378, 1973.
- 41
-
J. E. Hopcroft and R. E. Tarjan.
Efficient planarity testing.
Journal of the ACM, 21(4):549-568, 1974.
- 42
-
HP-UX process management white paper, version 1.3, 1997.
Available from:
http://h21007.www2.hp.com/portal/download/files/prot/files/STK/pdfs/proc_mgt.pdf [cited 2011-07-20].
- 43
-
M. S. Jensen and R. Pagh.
Optimality in external memory hashing.
Algorithmica, 52(3):403-411, 2008.
- 44
-
P. Kirschenhofer, C. Martinez, and H. Prodinger.
Analysis of an optimized search algorithm for skip lists.
Theoretical Computer Science, 144:199-220, 1995.
- 45
-
P. Kirschenhofer and H. Prodinger.
The path length of random skip lists.
Acta Informatica, 31:775-792, 1994.
- 46
-
D. Knuth.
Fundamental Algorithms, volume 1 of The Art of Computer
Programming.
Addison-Wesley, third edition, 1997.
- 47
-
D. Knuth.
Seminumerical Algorithms, volume 2 of The Art of Computer
Programming.
Addison-Wesley, third edition, 1997.
- 48
-
D. Knuth.
Sorting and Searching, volume 3 of The Art of Computer
Programming.
Addison-Wesley, second edition, 1997.
- 49
-
C. Y. Lee.
An algorithm for path connection and its applications.
IRE Transaction on Electronic Computers, EC-10(3):346-365,
1961.
- 50
-
E. Lehman, F. T. Leighton, and A. R. Meyer.
Mathematics for Computer Science.
2011.
Available from:
http://courses.csail.mit.edu/6.042/spring12/mcsfull.pdf [cited
2012-03-22].
- 51
-
C. Martínez and S. Roura.
Randomized binary search trees.
Journal of the ACM, 45(2):288-323, 1998.
- 52
-
E. F. Moore.
The shortest path through a maze.
In Proceedings of the International Symposium on the Theory of
Switching, pages 285-292, 1959.
- 53
-
J. I. Munro, T. Papadakis, and R. Sedgewick.
Deterministic skip lists.
In Proceedings of the third annual ACM-SIAM symposium on
Discrete algorithms (SODA'92), pages 367-375, Philadelphia, PA, USA, 1992.
Society for Industrial and Applied Mathematics.
- 54
-
Oracle.
The Collections Framework.
Available from:
http://download.oracle.com/javase/1.5.0/docs/guide/collections/ [cited
2011-07-19].
- 55
-
Oracle.
Java Platform Standard Ed. 6.
Available from: http://download.oracle.com/javase/6/docs/api/ [cited 2011-07-19].
- 56
-
Oracle.
The Java Tutorials.
Available from: http://download.oracle.com/javase/tutorial/ [cited 2011-07-19].
- 57
-
R. Pagh and F.F. Rodler.
Cuckoo hashing.
Journal of Algorithms, 51(2):122-144, 2004.
- 58
-
T. Papadakis, J. I. Munro, and P. V. Poblete.
Average search and update costs in skip lists.
BIT, 32:316-332, 1992.
- 59
-
M. Ptracu and M. Thorup.
Randomization does not help searching predecessors.
In N. Bansal, K. Pruhs, and C. Stein, editors, Proceedings of
the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007,
New Orleans, Louisiana, USA, January 7-9, 2007, pages 555-564. SIAM, 2007.
- 60
-
W. Pugh.
A skip list cookbook.
Technical report, Institute for Advanced Computer Studies, Department
of Computer Science, University of Maryland, College Park, 1989.
Available from: ftp://ftp.cs.umd.edu/pub/skipLists/cookbook.pdf [cited 2011-07-20].
- 61
-
W. Pugh.
Skip lists: A probabilistic alternative to balanced trees.
Communications of the ACM, 33(6):668-676, 1990.
- 62
-
M. Ptracu and M. Thorup.
The power of simple tabulation hashing, 2010.
http://arxiv.org/abs/1011.5200 arXiv:1011.5200.
- 63
-
Redis.
Available from: http://redis.io/ [cited 2011-07-20].
- 64
-
B. Reed.
The height of a random binary search tree.
Journal of the ACM, 50(3):306-332, 2003.
- 65
-
S. M. Ross.
Probability Models for Computer Science.
Academic Press, Inc., Orlando, FL, USA, 2001.
- 66
-
R. Sedgewick.
Left-leaning red-black trees, September 2008.
Available from:
http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf [cited 2011-07-21].
- 67
-
R. Seidel and C.R. Aragon.
Randomized search trees.
Algorithmica, 16(4):464-497, 1996.
- 68
-
H. H. Seward.
Information sorting in the application of electronic digital
computers to business operations.
Master's thesis, Massachusetts Institute of Technology, Digital
Computer Laboratory, 1954.
- 69
-
SkipDB.
Available from: http://dekorte.com/projects/opensource/SkipDB/ [cited 2011-07-20].
- 70
-
D.D. Sleator and R.E. Tarjan.
Self-adjusting binary trees.
In Proceedings of the 15th Annual ACM Symposium on Theory of
Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 235-245.
ACM, ACM, 1983.
- 71
-
S. P. Thompson.
Calculus Made Easy.
MacMillan, Toronto, 1914.
Project Gutenberg EBook 33283.
Available from: http://www.gutenberg.org/ebooks/33283 [cited
2012-06-14].
- 72
-
Peter van Emde Boas.
Preserving order in a forest in less than logarithmic time and linear
space.
Information Processing Letters, 6(3):80-82, 1977.
- 73
-
J. Vuillemin.
A data structure for manipulating priority queues.
Communications of the ACM, 21(4):309-315, 1978.
- 74
-
J. Vuillemin.
A unifying look at data structures.
Communications of the ACM, 23(4):229-239, 1980.
- 75
-
D. E. Willard.
Log-logarithmic worst-case range queries are possible in space
theta(n).
Information Processing Letters, 17(2):81-84, 1983.
- 76
-
J.W.J. Williams.
Algorithm 232: Heapsort.
Communications of the ACM, 7(6):347-348, 1964.
opendatastructures.org