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:
  1. 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
    }
    
  2. 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.
  3. Suffix Trees


For the remaining lectures, the following papers are relevant:
  1. F.P. Preparata and M.I. Shamos, "The Segment Tree" , Computational Geometry, Springer-Verlag, pp. 13-15, 1985.
  2. E. McCreight, "Priority Search Trees", SIAM J. Computing, Vol. 14-2, pp. 257-276, 1985.
  3. J. Bentley, "Data Structures for Range Searching", ACM Computing Surveys, Vol. 11-4, pp. 397-409, 1979.
  4. 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:
  1. Analysis of Fibonacci heaps.
  2. From 2-3-4 Trees to Red-Black Trees.
  3. Patricia.