Michael H. Goldwasser - Data Structures and Algorithms in Python

The design and analysis of efficient data structures has long been recognized as a vital subject in computing and is part of the core curriculum of computer science and computer engineering undergraduate degrees. Data Structures and Algorithms in Python provides an introduction to data structures and algorithms, including their design, analysis, and implementation. This book is designed for use in a beginning-level data structures course, or in an intermediate-level introduction to algorithms course. We discuss its use for such courses in more detail later in this preface.

To promote the development of robust and reusable software, we have tried to take a consistent object-oriented viewpoint throughout this text. One of the main ideas of the object-oriented approach is that data should be presented as being encapsulated with the methods that access and modify them. That is, rather than simply viewing data as a collection of bytes and addresses, we think of data objects as instances of an abstract data type (ADT), which includes a repertoire of methods for performing operations on data objects of this type. We then emphasize that there may be several different implementation strategies for a particular ADT, and explore the relative pros and cons of these choices. We provide complete Python implementations for almost all data structures and algorithms discussed, and we introduce important object-oriented design patterns as means to organize those implementations into reusable components.

Desired outcomes for readers of our book include that:

• They have knowledge of the most common abstractions for data collections (e.g., stacks, queues, lists, trees, maps).
• They understand algorithmic strategies for producing efficient realizations of common data structures.
• They can analyze algorithmic performance, both theoretically and experimentally, and recognize common trade-offs between competing strategies.
• They can wisely use existing data structures and algorithms found in modern programming language libraries.
• They have experience working with concrete implementations for most foundational data structures and algorithms.
• They can apply data structures and algorithms to solve complex problems.

In support of the last goal, we present many example applications of data structures throughout the book, including the processing of file systems, matching of tags in structured formats such as HTML, simple cryptography, text frequency analysis, automated geometric layout, Huffman coding, DNA sequence alignment, and search engine indexing.

This book is based upon the book Data Structures and Algorithms in Java by Goodrich and Tamassia, and the related Data Structures and Algorithms in C++ by Goodrich, Tamassia, and Mount. However, this book is not simply a translation of those other books to Python. In adapting the material for this book, we have significantly redesigned the organization and content of the book as follows:

• The code base has been entirely redesigned to take advantage of the features of Python, such as use of generators for iterating elements of a collection.
• Many algorithms that were presented as pseudo-code in the Java and C++ versions are directly presented as complete Python code.
• In general, ADTs are defined to have consistent interface with Python's built in data types and those in Python's collections module.
• serves as an additional reference regarding the functionality of the str class.
• Over 450 illustrations have been created or revised.
• New and revised exercises bring the overall total number to 750.

This book is accompanied by an extensive set of online resources, which can be found at the following Web site:

www.wiley.com/college/goodrich

Students are encouraged to use this site along with the book, to help with exercises and increase understanding of the subject. Instructors are likewise welcome to use the site to help plan, organize, and present their course materials. Included on this Web site is a collection of educational aids that augment the topics of this book, for both students and instructors. Because of their added value, some of these online resources are password protected.

For all readers, and especially for students, we include the following resources:

• All the Python source code presented in this book.
• PDF handouts of Powerpoint slides (four-per-page) provided to instructors.
• A database of hints to all exercises, indexed by problem number.

For instructors using this book, we include the following additional teaching aids: