Seminar in Algorithms (0368.434.301)
Spring
07/08
The seminar will focus on I/O efficient and cache oblivious algorithms.
Guidelines
The Input/Output Complexity of Sorting and Related Problems,
A. Aggarwal and J. S. Vitter
Optimal external memory interval management,
L. Arge and J. S. Vitter
The Buffer Tree: A Technique for Designing Batched External Data Structures,
L. Arge
Presentation by Or Ozery
I/O efficient point location using persistent B-trees,
L. Arge, A. Danner, and S. Teh
Presentation by Michal Balas
On external-memory MST, SSSP and multi-way planar graph separation
, L. Arge, G. Brodal, and L. Toma
Presentation by Dudu Lazarov (MST)
(Separators)
Cache-Oblivious Algorithms,
M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran
Presentation by Yuri
A locality-preserving cache-oblivious dynamic dictionary
M. A. Bender, Z. Duan, J. Iacono, J. Wu
Presentation by Andrey Stolyarenko
An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms,
L. Arge, M. A. Bender, E. D. Demaine, B. Holland-Minkley, and J. I. Munro
Presentation by Adam Sheffer
External-Memory Graph Algorithms
. Y-J. Chiang, M. T. Goodrich, E.F. Grove, R. Tamassia. D. E. Vengroff, and J. S. Vitter
A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms
, L. Arge,
M. Knudsen, and K. Larsen
Lower bounds for external memory dictionaries
, G. Brodal, and R. Fagerberg
On the limits of cache-obliviousness
, G. Brodal, and R. Fagerberg
Other material:
Arge and Bordal's course on I/O efficient algorithms
A survey on cache oblivious algorithms
by Arge, Brodal, and Fagerberg