Data Structures and Algorithms in Python

This all-new Data Structures and Algorithms in Python is designed to provide an introduction to data structures and algorithms, including their design, analysis, and implementation. The authors take advantage of the beauty and simplicity of Python to present executable source code that is clear and concise. Furthermore, a consistent object-oriented viewpoint is retained throughout the book, including the use of inheritance, both to maximize code reuse and to draw attention to the clear similarities and differences of various abstract data types and algorithmic approaches. Cover......Page 1 Title Page......Page 3 Copyright Page......Page 4 Preface......Page 7 Contents......Page 13 1 Python Primer......Page 23 1.1.1 The Python Interpreter......Page 24 1.1.2 Preview of a Python Program......Page 25 1.2.1 Identifiers, Objects, and the Assignment Statement......Page 26 1.2.2 Creating and Using Objects......Page 28 1.2.3 Python’s Built-In Classes......Page 29 1.3 Expressions, Operators, and Precedence......Page 34 1.3.1 Compound Expressions and Operator Precedence......Page 39 1.4.1 Conditionals......Page 40 1.4.2 Loops......Page 42 1.5 Functions......Page 45 1.5.1 Information Passing......Page 46 1.5.2 Python’s Built-In Functions......Page 50 1.6.1 Console Input and Output......Page 52 1.6.2 Files......Page 53 1.7 Exception Handling......Page 55 1.7.1 Raising an Exception......Page 56 1.7.2 Catching an Exception......Page 58 1.8 Iterators and Generators......Page 61 1.9.1 Conditional Expressions......Page 64 1.9.2 Comprehension Syntax......Page 65 1.9.3 Packing and Unpacking of Sequences......Page 66 1.10 Scopes and Namespaces......Page 68 1.11 Modules and the Import Statement......Page 70 1.11.1 Existing Modules......Page 71 1.12 Exercises......Page 73 2 Object-Oriented Programming......Page 78 2.1.1 Object-Oriented Design Goals......Page 79 2.1.2 Object-Oriented Design Principles......Page 80 2.1.3 Design Patterns......Page 83 2.2.1 Design......Page 84 2.2.3 Coding Style and Documentation......Page 86 2.2.4 Testing and Debugging......Page 89 2.3.1 Example: CreditCard Class......Page 91 2.3.2 Operator Overloading and Python’s Special Methods......Page 96 2.3.3 Example: Multidimensional Vector Class......Page 99 2.3.4 Iterators......Page 101 2.3.5 Example: Range Class......Page 102 2.4 Inheritance......Page 104 2.4.1 Extending the CreditCard Class......Page 105 2.4.2 Hierarchy of Numeric Progressions......Page 109 2.4.3 Abstract Base Classes......Page 115 2.5.1 Instance and Class Namespaces......Page 118 2.5.2 Name Resolution and Dynamic Dispatch......Page 122 2.6 Shallow and Deep Copying......Page 123 2.7 Exercises......Page 125 3 Algorithm Analysis......Page 131 3.1 Experimental Studies......Page 133 3.1.1 Moving Beyond Experimental Analysis......Page 135 3.2 The Seven Functions Used in This Book......Page 137 3.2.1 Comparing Growth Rates......Page 144 3.3.1 The “Big-Oh” Notation......Page 145 3.3.2 Comparative Analysis......Page 150 3.3.3 Examples of Algorithm Analysis......Page 152 3.4.2 The “Contra” Attack......Page 159 3.4.3 Induction and Loop Invariants......Page 160 3.5 Exercises......Page 163 4 Recursion......Page 170 4.1.1 The Factorial Function......Page 172 4.1.2 Drawing an English Ruler......Page 174 4.1.3 Binary Search......Page 177 4.1.4 File Systems......Page 179 4.2 Analyzing Recursive Algorithms......Page 183 4.3 Recursion Run Amok......Page 187 4.3.1 Maximum Recursive Depth in Python......Page 190 4.4.1 Linear Recursion......Page 191 4.4.2 Binary Recursion......Page 196 4.4.3 Multiple Recursion......Page 197 4.5 Designing Recursive Algorithms......Page 199 4.6 Eliminating Tail Recursion......Page 200 4.7 Exercises......Page 202 5 Array-Based Sequences......Page 205 5.1 Python’s Sequence Types......Page 206 5.2 Low-Level Arrays......Page 207 5.2.1 Referential Arrays......Page 209 5.2.2 Compact Arrays in Python......Page 212 5.3 Dynamic Arrays and Amortization......Page 214 5.3.1 Implementing a Dynamic Array......Page 217 5.3.2 Amortized Analysis of Dynamic Arrays......Page 219 5.3.3 Python’s List Class......Page 223 5.4.1 Python’s List and Tuple Classes......Page 224 5.4.2 Python’s String Class......Page 230 5.5.1 Storing High Scores for a Game......Page 232 5.5.2 Sorting a Sequence......Page 236 5.5.3 Simple Cryptography......Page 238 5.6 Multidimensional Data Sets......Page 241 5.7 Exercises......Page 246 6 Stacks, Queues, and Deques......Page 250 6.1 Stacks......Page 251 6.1.1 The Stack Abstract Data Type......Page 252 6.1.2 Simple Array-Based Stack Implementation......Page 253 6.1.3 Reversing Data Using a Stack......Page 257 6.1.4 Matching Parentheses and HTML Tags......Page 258 6.2 Queues......Page 261 6.2.1 The Queue Abstract Data Type......Page 262 6.2.2 Array-Based Queue Implementation......Page 263 6.3.1 The Deque Abstract Data Type......Page 269 6.3.2 Implementing a Deque with a Circular Array......Page 270 6.3.3 Deques in the Python Collections Module......Page 271 6.4 Exercises......Page 272 7 Linked Lists......Page 277 7.1 Singly Linked Lists......Page 278 7.1.1 Implementing a Stack with a Singly Linked List......Page 283 7.1.2 Implementing a Queue with a Singly Linked List......Page 286 7.2 Circularly Linked Lists......Page 288 7.2.1 Round-Robin Schedulers......Page 289 7.2.2 Implementing a Queue with a Circularly Linked List......Page 290 7.3 Doubly Linked Lists......Page 292 7.3.1 Basic Implementation of a Doubly Linked List......Page 295 7.3.2 Implementing a Deque with a Doubly Linked List......Page 297 7.4 The Positional List ADT......Page 299 7.4.1 The Positional List Abstract Data Type......Page 301 7.4.2 Doubly Linked List Implementation......Page 303 7.5 Sorting a Positional List......Page 307 7.6.1 Using a Sorted List......Page 308 7.6.2 Using a List with the Move-to-Front Heuristic......Page 311 7.7 Link-Based vs. Array-Based Sequences......Page 314 7.8 Exercises......Page 316 8 Trees......Page 321 8.1 General Trees......Page 322 8.1.1 Tree Definitions and Properties......Page 323 8.1.2 The Tree Abstract Data Type......Page 327 8.1.3 Computing Depth and Height......Page 330 8.2 Binary Trees......Page 333 8.2.1 The Binary Tree Abstract Data Type......Page 335 8.2.2 Properties of Binary Trees......Page 337 8.3.1 Linked Structure for Binary Trees......Page 339 8.3.2 Array-Based Representation of a Binary Tree......Page 347 8.3.3 Linked Structure for General Trees......Page 349 8.4.1 Preorder and Postorder Traversals of General Trees......Page 350 8.4.2 Breadth-First Tree Traversal......Page 352 8.4.3 Inorder Traversal of a Binary Tree......Page 353 8.4.4 Implementing Tree Traversals in Python......Page 355 8.4.5 Applications of Tree Traversals......Page 359 8.4.6 Euler Tours and the Template Method Pattern......Page 363 8.5 Case Study: An Expression Tree......Page 370 8.6 Exercises......Page 374 9 Priority Queues......Page 384 9.1.1 Priorities......Page 385 9.1.2 The Priority Queue ADT......Page 386 9.2.1 The Composition Design Pattern......Page 387 9.2.2 Implementation with an Unsorted List......Page 388 9.2.3 Implementation with a Sorted List......Page 390 9.3.1 The Heap Data Structure......Page 392 9.3.2 Implementing a Priority Queue with a Heap......Page 394 9.3.4 Python Heap Implementation......Page 398 9.3.5 Analysis of a Heap-Based Priority Queue......Page 401 9.3.6 Bottom-Up Heap Construction......Page 402 9.3.7 Python’s heapq Module......Page 406 9.4 Sorting with a Priority Queue......Page 407 9.4.1 Selection-Sort and Insertion-Sort......Page 408 9.4.2 Heap-Sort......Page 410 9.5.1 Locators......Page 412 9.5.2 Implementing an Adaptable Priority Queue......Page 413 9.6 Exercises......Page 417 10 Maps, Hash Tables, and Skip Lists......Page 423 10.1 Maps and Dictionaries......Page 424 10.1.1 The Map ADT......Page 425 10.1.2 Application: Counting Word Frequencies......Page 427 10.1.3 Python’s MutableMapping Abstract Base Class......Page 428 10.1.4 Our MapBase Class......Page 429 10.1.5 Simple Unsorted Map Implementation......Page 430 10.2 Hash Tables......Page 432 10.2.1 Hash Functions......Page 433 10.2.2 Collision-Handling Schemes......Page 439 10.2.3 Load Factors, Rehashing, and Efficiency......Page 442 10.2.4 Python Hash Table Implementation......Page 444 10.3 Sorted Maps......Page 449 10.3.1 Sorted Search Tables......Page 450 10.3.2 Two Applications of Sorted Maps......Page 456 10.4 Skip Lists......Page 459 10.4.1 Search and Update Operations in a Skip List......Page 461 10.4.2 Probabilistic Analysis of Skip Lists......Page 465 10.5.1 The Set ADT......Page 468 10.5.2 Python’s MutableSet Abstract Base Class......Page 470 10.5.3 Implementing Sets, Multisets, and Multimaps......Page 472 10.6 Exercises......Page 474 11 Search Trees......Page 481 11.1 Binary Search Trees......Page 482 11.1.1 Navigating a Binary Search Tree......Page 483 11.1.2 Searches......Page 485 11.1.3 Insertions and Deletions......Page 487 11.1.4 Python Implementation......Page 490 11.1.5 Performance of a Binary Search Tree......Page 495 11.2 Balanced Search Trees......Page 497 11.2.1 Python Framework for Balancing Search Trees......Page 500 11.3 AVL Trees......Page 503 11.3.1 Update Operations......Page 505 11.3.2 Python Implementation......Page 510 11.4.1 Splaying......Page 512 11.4.2 When to Splay......Page 516 11.4.3 Python Implementation......Page 518 11.4.4 Amortized Analysis of Splaying......Page 519 11.5.1 Multiway Search Trees......Page 524 11.5.2 (2,4)-Tree Operations......Page 527 11.6 Red-Black Trees......Page 534 11.6.1 Red-Black Tree Operations......Page 536 11.6.2 Python Implementation......Page 547 11.7 Exercises......Page 550 12 Sorting and Selection......Page 558 12.1 Why Study Sorting Algorithms?......Page 559 12.2.1 Divide-and-Conquer......Page 560 12.2.2 Array-Based Implementation of Merge-Sort......Page 565 12.2.3 The Running Time of Merge-Sort......Page 566 12.2.4 Merge-Sort and Recurrence Equations......Page 568 12.2.5 Alternative Implementations of Merge-Sort......Page 569 12.3 Quick-Sort......Page 572 12.3.1 Randomized Quick-Sort......Page 579 12.3.2 Additional Optimizations for Quick-Sort......Page 581 12.4.1 Lower Bound for Sorting......Page 584 12.4.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort......Page 586 12.5 Comparing Sorting Algorithms......Page 589 12.6.1 Sorting According to a Key Function......Page 591 12.7.1 Prune-and-Search......Page 593 12.7.2 Randomized Quick-Select......Page 594 12.7.3 Analyzing Randomized Quick-Select......Page 595 12.8 Exercises......Page 596 13 Text Processing......Page 603 13.1 Abundance of Digitized Text......Page 604 13.1.1 Notations for Strings and the Python str Class......Page 605 13.2.1 Brute Force......Page 606 13.2.2 The Boyer-Moore Algorithm......Page 608 13.2.3 The Knuth-Morris-Pratt Algorithm......Page 612 13.3.1 Matrix Chain-Product......Page 616 13.3.2 DNA and Text Sequence Alignment......Page 619 13.4 Text Compression and the Greedy Method......Page 623 13.4.1 The Huffman Coding Algorithm......Page 624 13.4.2 The Greedy Method......Page 625 13.5.1 Standard Tries......Page 626 13.5.2 Compressed Tries......Page 630 13.5.3 Suffix Tries......Page 632 13.5.4 Search Engine Indexing......Page 634 13.6 Exercises......Page 635 14 Graph Algorithms......Page 641 14.1 Graphs......Page 642 14.1.1 The Graph ADT......Page 648 14.2 Data Structures for Graphs......Page 649 14.2.1 Edge List Structure......Page 650 14.2.2 Adjacency List Structure......Page 652 14.2.3 Adjacency Map Structure......Page 654 14.2.4 Adjacency Matrix Structure......Page 655 14.2.5 Python Implementation......Page 656 14.3 Graph Traversals......Page 660 14.3.1 Depth-First Search......Page 661 14.3.2 DFS Implementation and Extensions......Page 666 14.3.3 Breadth-First Search......Page 670 14.4 Transitive Closure......Page 673 14.5.1 Topological Ordering......Page 677 14.6.1 Weighted Graphs......Page 681 14.6.2 Dijkstra’s Algorithm......Page 683 14.7 Minimum Spanning Trees......Page 692 14.7.1 Prim-Jarník Algorithm......Page 694 14.7.2 Kruskal’s Algorithm......Page 698 14.7.3 Disjoint Partitions and Union-Find Structures......Page 703 14.8 Exercises......Page 708 15 Memory Management and B-Trees......Page 719 15.1 Memory Management......Page 720 15.1.1 Memory Allocation......Page 721 15.1.2 Garbage Collection......Page 722 15.1.3 Additional Memory Used by the Python Interpreter......Page 725 15.2.1 Memory Systems......Page 727 15.2.2 Caching Strategies......Page 728 15.3 External Searching and B-Trees......Page 733 15.3.1 (a,b) Trees......Page 734 15.3.2 B-Trees......Page 736 15.4 External-Memory Sorting......Page 737 15.4.1 Multiway Merging......Page 738 15.5 Exercises......Page 739 A Character Strings in Python......Page 743 B Useful Mathematical Facts......Page 747 Bibliography......Page 754 Index......Page 759 Based on the authors'market leading data structures books in Java and C++, this book offers a comprehensive, definitive introduction to data structures in Python by authoritative authors. Data Structures and Algorithms in Python is the first authoritative object-oriented book available for Python data structures. Designed to provide a comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation, the text will maintain the same general structure as Data Structures and Algorithms in Java and Data Structures and Algorithms in C++. Begins by discussing Python's conceptually simple syntax, which allows for a greater focus on concepts. Employs a consistent object-oriented viewpoint throughout the text. Presents each data structure using ADTs and their respective implementations and introduces important design patterns as a means to organize those implementations into classes, methods, and objects. Provides a thorough discussion on the analysis and design of fundamental data structures. Includes many helpful Python code examples, with source code provided on the website. Uses illustrations to present data structures and algorithms, as well as their analysis, in a clear, visual manner. Provides hundreds of exercises that promote creativity, help readers learn how to think like programmers, and reinforce important concepts. Contains many Python-code and pseudo-code fragments, and hundreds of exercises, which are divided into roughly 40% reinforcement exercises, 40% creativity exercises, and 20% programming projects. Based on the authors' market leading data structures books in Java and C++, this textbook offers a comprehensive, definitive introduction to data structures in Python by respected authors. Data Structures and Algorithms in Python is the first mainstream object-oriented book available for the Python data structures course. Designed to provide a comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation, the text will maintain the same general structure as Data Structures and Algorithms in Java and Data Structures and Algorithms in C++. This textbook offers a comprehensive, definitive introduction to data structures in Python by respected authors. It is the first mainstream object-oriented book available not only for the Python data structures course, but also provides a comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation Based on the authors market leading data structures books in Java and C++, this book offers a comprehensive, definitive introduction to data structures in Python by authoritative authors. Data Structures and Algorithms in Python is the first authoritative object-oriented book available for Python data structures. Many algorithms that were presented as pseudo-code in Java and C++ versions are directly presented as complete Python code ; in general abstract data type (ADT) are defined to have consistent interface with Python's collections module ; separate intoduction to object-oriented programming in Python