CPS 238 I/O-Efficient Algorithms
Description:
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.
Lectures:
Thursdays 5:25-8:15 in D243.
Instructor:
Lars Arge
Office: D205 LSRC Bldg
Phone: 660-6557
E-mail: large@cs.duke.edu
Prerequisites:
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.
Course material:
The course will be based on original papers, survey papers and lecture
notes.
Course Synopsis:
-
Hierachical memory, I/O-model and fundamental bounds
-
External sorting and searching: Merging, distribution, B-trees (including weight-balanced and persistant),
Buffer-trees, lower bounds
-
Geometric searching problems: Interval trees, point location,
priority search trees, range trees, kdB-trees, O-trees, practical efficient
multipurpose structures
-
Batched geometric problems: Distribution sweeping, batched filtering,
line segment intersection, lower bounds
-
Graph problems: List ranking, basic tree and traversal algorithms, minimum spanning tree and shortest
path algorithms, planer graph algorithms, lower bounds, graph blocking
-
Cache-oblivious algorithms
-
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:
Grading will be based on a combination of some of the
following; homework, class participation, class presentations, and a term
paper/project.
Lars Arge
Fri Jan 16 2004