Peter Brass
Data Structures
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 pointsare 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
Peter Brass: Advanced Data Structures, Cambridge University Press 2008.
There will be four implementation homeworks of structures; test code
will be provided, and homework submissions are not accepted until
they pass this test. Programs are to be written in C or C++. and will
be tested in a linux environment using gcc/g++.
Peter Brass
(
peter@cs.ccny.cuny.edu),
Department of Computer Science, City College, CUNY, New York