UNIVERSITY OF AARHUS
DEPARTMENT OF COMPUTER SCIENCE

Pensum: External Memory Algorithms and Data Structures, Fall 1999

1. [A97] External-Memory Algorithms with Applications in Geographic Information Systems , Lars Arge. In Algorithmic Foundations of Geographic Information Systems , M. van Kreveld, J. Nievergelt, T. Roos and P. Widmayer (Eds.), LNCS Tutorial, Lecture Notes in Computer Science Vol. 1340, Springer-Verlag, 1997. Pages 1-6
2. [GT98] Data Structures and Algorithms in JAVA , Michael T. Goodrich and Roberto Tamassia, John Wiley & Sons, Inc, 1998. Pages 523-524, 658-664
3. [F99] Amortisered analyse af (a,b)-træer, Rolf Fagerberg, Note, 1999. All
4. [FJKT99] Heaps and heapsort on secondary storage, R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola. Theoretical Computer Science 220 (1999), 345-362 All
5. [A95] The Buffer Tree: A New Technique for Optimal I/O Algorithms , L. Arge. Full version of the paper appearing in Proceedings of Fourth Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science Vol. 955, Springer-Verlag, 1995, 334-345. All
6. [KL92] I/O-complexity of comparison and permutation problems . Mikael Knuden and Kirsten Larsen. Master Thesis, DAIMI, November 1992. Sec. 1, 2, 3.1, 3.2, 4.1, 4.2
7. [S98] Random Permutations on Distributed, External and Hierarchical Memory, Peter Sanders. Information Processing Letters 56 (1998) 305-309. All
8. [ASV99] On-Two Dimensional Indexability and Optimal Range Search Indexing , Lars Arge, Vasilis Samoladas, and Jeffrey Scott Vitter. In Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1999 All
9. [AV96] Optimal Dynamic Interval Management in External Memory , Lars Arge and Jeffrey Scott Vitter. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996, 560-569. All
10. [AVV95] External-Memory Algorithms for Processing Line Segments in Geographic Information Systems , Lars Arge, Darren Vengroff and Jeff Vitter. In Proceedings of the Third European Symposium on Algorithms, Lecture Notes in Computer Science Vol. 979, Springer-Verlag, 1995, 295-310. All
11. [AHVV99] Efficient Bulk Operations on Dynamic R-trees , Lars Arge, Klaus Hinrichs, Jan Vahrenhold, and Jeff Vitter. In Proceedings ALENEX '99, 1999. All
12. [FG99] The String B-tree: A New Data Structure for String Search in External Memory and its Applications , Paolo Ferragina, and Roberto Grossi. Journal of the ACM, 46(2), 1999, 236-280. Pages 236-266, 267-269, 271-280
13. [AFGV97] On Sorting Strings in External Memory , Lars Arge, Paolo Ferragina, Roberto Grossi, and Jeff Vitter. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, 540-548. Sec. 1-3,5
14. [ABW98] A Functional Approach to External Graph Algorithms, James Abello, Adam L. Buchsbaum, and Jeffrey R. Westbrook. In Proceedings of the 6th Annual European Symposium on Algorithms, Lecture Notes in Computer Science Vol. 1461, Springer-Verlag, 1998, 332-43. Sec. 1-4, 6
15. [MR99] I/O-Complexity of Graph Algorithms , Kameshwar Munagala and Abhiram Ranade. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, 687-694. Sec. 5

Projects






StudentGerth Stølting BrodalRolf Fagerberg