Pre-requisites : CS204

Syllabus :
Hierarchical memory levels performance characteristics Parallel disk model. Fundamental I/O operations. Design and analysis of efficient external memory algorithms for some representative problems. Sorting, permutation, searching. Depth first search, breadth first search, Minimum spanning forest, connected components, single source shortest path, transitive closure. hashing, string matching. External Memory Data Structures. Cache efficient algorithms. Applications in various areas, for example, Computational geometry.

Texts :

References :
1. J. S. Vitter. External Memory Algorithms and Data Structures: Dealing with MASSIVE DATA, ACM Computing Surveys, 33(2), June 2001, 209-271.
2. Course Material on External Memory Algorithms and Data Structures: http://www.brics.dk/~gerth/emF99/
3. Other research papers.