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.,

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 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 (,

Department of Computer Science, City College, CUNY, New York