CPS 238 I/O-Efficient Algorithms
In this course we consider the design and analysis of I/O-efficient (or
external memory) algorithms and data structures for problems involving
massive amounts of data.
Thursdays 5:10-7:40 in D344 (note the changed time!)
Office: D205 LSRC Bldg
CPS230 (or equivalent) and an interest in algorithms. Undergraduates who
have taken CPS130 and are intersted in taking this class is encouraged
to contact Lars Arge.
The course will be based on original papers, survey papers and lecture
Two-level I/O-model and fundamental bounds
External sorting and searching: Merging, distribution, B-trees,
Buffer-trees, lower bounds
Graph problems: Connection to PRAM algorithms, list ranking, tree
algorithms, basic traversal algorithms, Minimum spanning tree and shortest
path algorithms, planer graph algorithms, lower bounds, graph blocking
Batched geometric problems: Distribution sweeping, batched filtering,
line segment intersection, lower bounds
Geometric searching problems: Weight-balanced and persistent B-trees,
interval trees, point location, priority search trees, range trees, cross
trees, practical efficient multipurpose structures
Models of hierachical memory
Implementing I/O algorithms and data structures
Summary of Lectures:
A summary of the lectures held so far, a list of the material covered,
handouts, along with information about what is approximately going to happen
in the next lectures, can be found here.
Grading will be based on a combination of some of the following; homework,
class participation, class presentations, and a term paper/project.
Fri Nov 16 2001