CPS 238 I/OEfficient Algorithms
Description:
In this course we consider the design and analysis of I/Oefficient (or
external memory) algorithms and data structures for problems involving
massive amounts of data.
Lectures:
Thursdays 5:107:40 in D344 (note the changed time!)
Instructor:
Lars Arge
Office: D205 LSRC Bldg
Phone: 6606557
Email: 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:

Twolevel I/Omodel and fundamental bounds

External sorting and searching: Merging, distribution, Btrees,
Buffertrees, 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: Weightbalanced and persistent Btrees,
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