Course Content (Syllabus)
Algorithms and data structures with emphasis in massive data sets. External memory models. Algorithms and data structures for two level model (B-trees, Computational geometry algorithms in external memory, string algorithms in external memory). Algorithms and data structures for the Cache Oblivious model (Cache Oblivious B-trees). Advanced hashing techniques. Predecessor structures. Algorithms for data compression. Algorithms for the streaming model. Data structures in P2P networks (overlays).
External Memory, Streaming model, Compression, Predecessor problem, Hashing
Additional bibliography for study
1. J. Abello, P.M. Pardalos and M.G.C. Resende (editors). Handbook of Massive Data Sets. Kluwer Academic Publishers. 2002, ISBN: 1-4020-0489-3.
2. D. Menta and S Sahni, Handbook of Data Structures and Application. 2005, ISBN 1-5848-8435-5
3. J. Vitter, Algorithms and Data Structures for External Memory, Book, (http://www.ittc.ku.edu/~jsv/Papers/Vit.IO_book.pdf)
4. External Memory Geometric Data Structures. L. Arge, Duke University Lecture notes
5. Erik Demaine, Cache Oblivious Algorithms and Data-Structures, in Lecture Notes from the EEF Summer School on Massive Data Sets, Lecture Notes in Computer Science, BRICS, University of Aarhus, Denmark, June 27-July 1, 2002, (http://erikdemaine.org/papers/BRICS2002/)
6. *Muthu Muthukrishnan, Data Streams: Algorithms and Applications (ebook) (http://algo.research.googlepages.com/eight.ps)