Python Data Structures and Algorithm Analysis (2nd Edition)

This book is a classic textbook on data structures and algorithms using Python. It covers Python fundamentals review, algorithm analysis (Big O notation), basic data structures (stacks, queues, lists), recursion, searching and sorting, tree and graph algorithms. Through practical code listings, it helps readers understand how to efficiently implement various abstract data types using Python.

Only by deeply understanding data structures and algorithms can one truly master Python.

Author: Bradley N. Miller (Professor Emeritus of Computer Science, Franklin & Marshall College, USA), David L. Ranum (Cognitive Software Engineer at IBM Watson)

Acknowledgments: Thanks to colleague Steve Hubbard for extensive feedback on the first edition and new material for this edition, as well as to peers worldwide who emailed us with corrections and suggestions. Special thanks to Mary, Bob, and others at Java John’s Café in Decatur for allowing us to become "resident authors" during our sabbaticals. Also, heartfelt gratitude to the staff at Franklin, Beedle & Associates (especially Jim Leisy and Tom Sumner) for their enjoyable collaboration. Finally, special thanks to our wives, Jane Miller and Brenda Ranum, whose love and support made this book possible.

1. Understand the relationship between computer science, algorithms, and programming, and grasp the concepts of Abstract Data Types (ADT) and information hiding.
2. Become proficient in Python's built-in collection data types (lists, tuples, sets, dictionaries) and control structures (loops, conditionals, exception handling).
3. Master core aspects of Python object-oriented programming: including class definition, constructors, operator overloading (e.g., fraction addition), application of Euclidean algorithm, and distinction between deep and shallow equality.
4. Compare multiple algorithmic approaches: explain four solutions for anagram detection (counting, sorting, brute force, counting) and their corresponding time complexities.
5. Quantify Python container performance: understand the Big O efficiency of core operations in Python lists (List) and dictionaries (Dict), and distinguish performance differences between pop() and pop(i).
6. Develop performance validation skills: use the timeit module to design experiments verifying consistency between theoretical complexity and actual runtime.
7. Understand and differentiate the logical characteristics of linear data structures (stacks, queues, deques, lists).
8. Implement custom stacks, queues, and deques using Python's basic collections (e.g., lists).
9. Apply stacks in expression processing (infix to postfix conversion, postfix evaluation) and queues in system simulation (printer simulation).
10. Master the three fundamental principles of recursion: accurately identify and write recursive functions containing base cases, state evolution, and self-calls.