References
Pointers to free electronic papers were mined from CiteSeer, Google Scholar, and authors' personal web pages. Papers from the ACM Digital Library and most journals require a subscription, and thus may be inaccessible from off-campus; I will only link to these if no free version is available.
*Stars indicate authors who (as far as I know) were graduate students when the paper was published. **Double stars indicate undergraduate authors. [No pressure!]
Surveys and monographs
- [AE99]
- Pankaj K. Agarwal and
Jeff Erickson.
Geometric range seraching and its relatives.
Advances in Discrete and Computational Geometry
(Bernard
Chazelle, Jacob
E. Goodman, and
Richard
Pollack, editors), 1-56, 1999.
Contemporary Mathematics 223, AMS Press.
- [G05]
- Leonidas
Guibas.
Kinetic data structures.
Chapter 23 of Handbook of Data Structures and Applications
(Dinesh P. Mehta and Sartaj Sahni, eds.), 23-1–23-18.
Chapman and Hall/CRC, 2005.
- [M99]
- Peter Bro Miltersen.
Cell probe complexity: A survey.
Manuscript, 1999.
[Powerpoint slides]
- [O83]
- Mark H. Overmars.
The Design of Dynamic Data Structures.
Lecture Notes in Computer Science 156, Spring-Verlag, 1983.
- [T83]
- Robert E. Tarjan.
Data Structures and Network Algorithms.
CBMS-NSF Regional Conference Series in Applied Mathematics 44,
SIAM, 1983.
Papers
- [AH97]
-
Susanne Albers* and
Torben Hagerup.
Improved parallel integer sorting without concurrent writing.
Information and Computation 136:25-51, 1997.
- [AHLT05]
- Stephen Alstrup,
Jacob Holm*,
Kristian de Lichtenberg*,
and
Mikkel Thorup.
Maintaining information in fully dynamic trees with top trees.
ACM Transactions on Algorithms 1(2):243-264, 2005.
- [A89]
- Arne Anderson.
Improving
partial rebuilding by using simple balance criteria.
Proc. Workshop on Algorithms and Data Structures, 393-402.
Lecture Notes in Computer Science 382, Springer-Verlag, 1989.
- [A99]
- Arne Anderson.
General balanced trees.
J. Algorithms 30:1-28, 1999.
- [AHNR98]
- Arne Anderson,
Torben Hagerup,
Stefan Nilsson*, and
Rajeev Raman.
Sorting in linear time?
J. Computer and System Sciences 57(1): 74-93, 1998.
- [AV96]
- Lars Arge* and
Jeffrey S. Vitter.
Optimal dynamic interval management in external memory.
Proc. 37th IEEE Symposium on Foundations of Computer Science,
560-569, 1996.
- [BGH99]
- Julien Basch*,
Leonidas
Guibas, and John Hershberger.
Data structures for mobile data.
J. Algorithms 31(1):1-28, 1999.
- [BGR03]
- Julien Basch*,
Leonidas
Guibas, and
G. D. Ramkumar*.
Reporting red-blue intersections between two sets of conencted line segments.
Algorithmica 35:1-20, 2003.
- [BF02]
- Paul Beame
and Faith E. Fich.
Optimal bounds for the predecessor problem and related problems.
Journal of Computer and System Sciences
65(1):38-72, 2002.
- [BW80]
- Jon L. Bentley
and
Herman Maurer.
Efficient worst-case data structures for range searching.
Acta Informatica 13:155-168, 1980.
- [BS80]
- Jon L. Bentley
and
James B. Saxe*.
Decomposable searching problems: 1. Static-to-dynamic transformations.
J. Algorithms 1:301-358, 1980.
- [BW80]
- Jon L. Bentley
and
Derick Wood.
An optimal algorithm for reporting intersections of rectangles.
IEEE Trans. Computers C-29:571-577, 1980.
- [C86]
- Bernard Chazelle.
Filtering search: A new approach to query answering.
SIAM J. Comput. 15:703-724, 1986.
- [CG86a]
- Bernard
Chazelle and
Leonidas J.
Guibas.
Fractional cascading: I. A data structuring technique.
Algorithmica 1:133-162, 1986.
[
Technical report version]
- [CG86b]
- Bernard
Chazelle and
Leonidas J.
Guibas.
Fractional cascading: II. Applications.
Algorithmica 1:163-191, 1986.
[
Technical report version]
- [DSW05]
- Jonathan Derryberry*,
Daniel D. Sleator,
and Chengwen Chris Wang*.
A lower bound framework for binary search trees with rotations.
Technical Report CMU-CS-05-187, Carnegie Mellon University,
November 22, 2005.
- [DHIP04]
- Erik D. Demaine,
Dion Harmon*,
John Iacono, and
Mihai Pătraşcu**.
Dynamic Optimality—Almost.
Proc. 45th IEEE Symposium on Foundations of Computer Science,
484--490, 2004.
Full version to appear in SIAM J. Computing
- [E75]
- Peter van Emde Boas.
Preserving order in a forest in less than logarithmic time.
Proc. 16th IEEE Symposium on Foundations of Computer Science, 75-84, 1975.
- [E83a]
- Herbert Edelsbrunner
A new approach to rectangle intersections, Part I.
Int. J. Computer Mathematics 13:209-219, 1983.
- [E83b]
- Herbert Edelsbrunner
A new approach to rectangle intersections, Part II.
Int. J. Computer Mathematics 13:221-229, 1983.
- [EM81]
- Herbert Edelsbrunner*
and Herman A. Maurer.
On the intersection of orthogonal objects.
Information Processing Letters 13:177-181, 1981.
- [FF02]
- Guilherme D. da Fonseca*
and Celina M. H. de Figueiredo.
Kinetic heap-ordered trees: tight analysis and faster algorithms.
Information Processing Letters 85(3):165-169, 2002.
- [F97]
- Greg Frederickson.
A data structure for dynamically maintaining rooted trees.
J. Algorithms 24:37-65, 1997.
- [FW93]
-
Michael L. Fredman and
Dan E. Willard.
Surpassing the information theoretic bound with fusion trees.
J. Computer and System Sciences 47(3):424-436, 1993.
Originally entitled "BLASTING Through The Information Theoretic
Barrier With FUSION TREES!!!1!11!!!eleven!!MCXI!!"
- [GR93]
- Igal Galperin* and
Ronald L. Rivest.
Scapegoat trees.
Proc. 4th ACM-SIAM Symposium on Discrete Algorithms,
165-174, 1993.
[ACM Digital Library]
- [HS74]
- Juris Hartmanis and
Janos Simon*.
On the power of multiplication in random access machines.
Proc. 15th IEEE Symposium on Switching and Automata Theory, 13-23, 1974.
- [HK99]
- Monika Rauch Henzinger
and
Valerie King.
Randomized fully dynamic graph algorithms with polylogarithmic time per operation.
J. ACM 46:502-516, 1999.
- [HLT01]
- Jacob Holm*,
Kristian de Lichtenberg*,
Mikkel Thorup.
Poly-logarithmic deterministic fully-dynamic algorithms
for connectivity, minimum spanning tree, 2-edge, and
biconnectivity.
Journal of thhe ACM 48(4):723-760, 2001.
[ACM Digital Library]
See also technical reports
DIKU-TR-97/17 and
DIKU-TR-97/26,
University of Copenhagen, September 1997.
- [I05]
- John Iacono.
Key independent optimality.
Algorithmica, 42:3--10, 2005.
- [KR84]
- David G Kirkpatrick and
Stefan Reisch*.
Upper bounds for sorting on random access machines.
Theoretical Computer Science 28:263-276, 1984.
- [M85]
- Edward M. McCreight.
Priority search trees.
SIAM J. Comput. 14(2):257-276, 1985.
- [OL81]
- Mark H. Overmars*
and
Jan van Leeuwen.
Maintenance of configurations in the plane.
J. Computer and System Sciences 23:166-204, 1981.
- [OL81a]
- Mark H. Overmars*
and
Jan van Leeuwen.
Worst-case optimal insertion and deletion methods for
decomposable searching problems.
Information Processing Letters 12(4):168-173, 1981.
- [PD06]
- Mihai Pătraşcu** and
Erik Demaine.
Logarithmic lower bounds in the cell-probe model.
To appear in SIAM J. Computing.
- [PT06]
- Mihai Pătraşcu** and
Mikkel Thorup.
Time-space
trade-offs for predecessor search.
To appear in Proc. 38th ACM Symposium on Theory of
Computing, 2006.
- [ST83]
- Daniel D. Sleator*
and
Robert E. Tarjan.
A data structure for dynamic trees.
J. Computer and System Sciences 26:362-391, 1983.
- [ST85]
- Daniel D. Sleator
and
Robert E. Tarjan.
Self-adjusting binary search trees.
J. ACM 32:652-686, 1985.
[HTML demo and C code]
- [TW05]
- Robert E. Tarjan
and
Renato Werneck*.
Self-adjusting top trees.
Proc. 16th ACM-SIAM Symposium on Discrete Algorithms,
813--822, 2005.
- [WDS06]
- Chengwen Chris Wang*.
Jonathan Derryberry*, and
Daniel D. Sleator.
O(loglog n)-competitive binary search trees.
Proc. 17th ACM-SIAM Symposium on Discrete Algorithms,
374-383, 2006.
- [W87]
- Robert E. Wilber*.
Lower bounds for accessing binary search trees with rotations.
SIAM J. Computing 18(1):56-67, 1987.
- [W83]
- Dan E. Willard.
Log-logarithmic worst-case range queries are possible in space
Θ(n).
Information Processing Letters 17(2):81-84 (1983).
See also these web pages for other advanced data structure courses: