COP 5536 / AD 711R
Advanced Data Structures
University of Florida
Instructional Material
Text:
None Required.
Many students find that
the lectures, powerpoint handouts, and prerecorded lectures, which are available from this Web site,
are sufficient to do well
in this course. All assignment questions are posted on the Web.
Supplementary sources, which will broaden your learning
experience, are listed below. Copies of these sources
are on reserve at the Science Library.
Supplementary Sources:
Most of the lectures are based on material contained in:
Fundamentals of data structures in C++, by E. Horowitz, S. Sahni,
and D. Mehta, Second Edition, Silicon Press, 2007.
Some of the lectures rely on the following Web material:
-
Amortized Complexity
This reading refers to a Program 2.10, which is given below:
void insert(int a[], int n, int x)
{// assume enough place for an insert
// find proper place for x
int i;
for (i = n - 1; i >= 0 && x < a[i]; i--)
a[i+1] = a[i];
a[i+1] = x; // insert x
}
-
K. Chong and S. Sahni,
Correspondence based data structures for double ended priority queues.
ACM Jr. on Experimental Algorithmics, Volume 5, 2000,
Article 2,
22 pages.
PDF File.
-
Suffix Trees
For the remaining lectures, the following papers are relevant:
-
F.P. Preparata and M.I. Shamos, "The Segment Tree" ,
Computational Geometry, Springer-Verlag, pp. 13-15,
1985.
-
E. McCreight, "Priority Search Trees", SIAM J.
Computing, Vol. 14-2, pp. 257-276, 1985.
-
J. Bentley, "Data Structures for Range Searching",
ACM Computing Surveys, Vol. 11-4, pp. 397-409, 1979.
-
Hanan Samet, "The Quadtree and Related
Hierarchical Data Structures", ACM Computing Surveys,
Vol. 16-2, pp. 187-229, 1986.
A fairly exhaustive reference on the subject of data structures is:
Handbook of data structures and applications. Dinesh Mehta and Sartaj Sahni, Editors. Chapman and Hall/CRC, 2005.
Supplementary lectures that you may find useful:
-
Analysis of Fibonacci heaps.
-
From 2-3-4 Trees to Red-Black Trees.
-
Patricia.