Terms and Conditions:

Dave Mount wrote:Copyright, David M. Mount, 2001, Dept. of Computer Science, University of Maryland, College Park, MD, 20742. These lecture notes were prepared by David Mount for the course CMSC 420, Data Structures, at the University of Maryland, College Park. Permission to use, copy, modify, and distribute these notes for educational purposes and without fee is hereby granted, provided that this copyright notice appear in all copies.

Excerpts from the Notes:

The study of data structures and the algorithms that manipulate them is among the most fundamental topics in computer science. Most of what computer systems spend their time doing is storing, accessing, and manipulating data in one form or another. Some examples from computer science include networking, information retrieval, compilers and computer graphics.

This course will deal with the first two tasks of storage and access at a very general level. (The last issue of manipulation is further subdivided into two areas, manipulation of numeric or floating point data, which is the subject of numerical analysis, and the manipulation of discrete data, which is the subject of discrete algorithm design.) A good understanding of data structures is fundamental to all of these areas.

Whenever we deal with the representation of real world objects in a computer program we must first consider a number of issues: modeling, operations, representation and algorithms. Note that the first two items are essentially mathematical in nature, and deal with the "what" of a data structure, whereas the last two items involve the implementation issues and the "how" of the data structure. The first two essentially encapsulate the essence of an abstract data type (or ADT). In contrast the second two items, the concrete issues of implementation, will be the focus of this course.

This course will explore a number of different data structures, study their implementations, and analyze their efficiency (both in time and space). One of the goals will be to provide the students with the tools that they will need to design and implement their own data structures to solve their own specific problems in data storage and retrieval.

Course Overview:

This course will consider many different abstract data types, and many different data structures for storing each type. Note that there will generally be many possible data structures for each abstract type, and there will not generally be a "best" one for all circumstances. It will be important for the student as a designer of data structures to understand each structure well enough to know the circumstances where one data structure is to be preferred over another.