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:10-7:40 in D344 (note the changed time!)
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:
-
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:
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 Nov 16 2001