Download
Introduction
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 beginninglevel 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
Contents and Organization
The chapters for this book are organized to provide a pedagogical path that starts with the basics of Python programming and object-oriented design. We then add foundational techniques like algorithm analysis and recursion. In the main portion of the book, we present fundamental data structures and algorithms, concluding with a discussion of memory management (that is, the architectural underpinnings of data structures). Specifically, the chapters for this book are organized as follows:
1. Python Primer
2. Object-Oriented Programming
3. Algorithm Analysis
4. Recursion
5. Array-Based Sequences
6. Stacks, Queues, and Deques
7. Linked Lists
8. Trees
9. Priority Queues
10. Maps, Hash Tables, and Skip Lists
11. Search Trees
12. Sorting and Selection
13. Text Processing
14. Graph Algorithms
15. Memory Management and B-Trees
A. Character Strings in Python
B. Useful Mathematical Facts
