Peter Brass
Advanced Data Structures
Graduate Course Fall 2006, Thursday 7.15-9.45 p.m.
Data structures are a building block for algorithms. A data structure models
some abstract structure with a specified set of operations, e.g.,
- maintaining a set under insertions, deletions, and find operations, or
- maintaining a linear order under insertions, deletions, and comparisons, or
- maintaining a graph under insertion of edges and queries whether two points
are in the same connected component, or
- answering orthogonal range queries for a point set, or
- answering substring queries for a string.
In each of these situations, we have a well-specified behavior of what
the structure should do, but it is not immediately clear how we should
achieve that behavior. This is an algorithmic question: to design and
analyze algorithms that realize the required operations, and answer questions
like
- How fast can we perform the operations ?
- Can we do better if we allow amortized complexity
instead of worst-case complexity ?
- How much space does the structure need ?
- Does the structure support changes, or only queries ?
- How can we access past versions of the structure?
Once we know good methods to realize these structures, they are available
as components to higher-level algorithms, like the heap in Dijkstra's
shortest-path algorithm, or the set-union strukture in Kruskal's minimum
spanning tree algorithm; whenever an algorithm performs such operations
often, one should look for the most efficient realization of that operation.
In this course we will study many data structures, their analysis and
implementation. The lectures will be based on my
book manuscript.
There will be several implementation homeworks in this class; knowledge of
C or C++ is required.
Peter Brass
(
peter@cs.ccny.cuny.edu),
Department of Computer Science, City College, CUNY, New York