£167.95

Description

Contents

Preface v 1 Python Primer 1 1.1 Python Overview 2 1.2 Objects in Python 4 1.3 Expressions, Operators, and Precedence 12 1.4 Control Flow 18 1.5 Functions 23 1.6 Simple Input and Output 30 1.7 Exception Handling 33 1.8 Iterators and Generators 39 1.9 Additional Python Conveniences 42 1.10 Scopes and Namespaces 46 1.11 Modules and the Import Statement 48 1.12 Exercises 51 2 Object-Oriented Programming 56 2.1 Goals, Principles, and Patterns 57 2.2 Software Development 62 2.3 Class Definitions 69 2.4 Inheritance 82 2.5 Namespaces and Object-Orientation 96 2.6 Shallow and Deep Copying101 2.7 Exercises 103 3 Algorithm Analysis 109 3.1 Experimental Studies 111 3.1.1 Moving Beyond Experimental Analysis 113 3.2 The Seven Functions Used in This Book 115 3.3 Asymptotic Analysis 123 3.4 Simple Justification Techniques 137 3.5 Exercises 141 4 Recursion 148 4.1 Illustrative Examples 150 4.2 Analyzing Recursive Algorithms 161 4.3 Recursion Run Amok 165 4.4 Further Examples of Recursion 169 4.5 Designing Recursive Algorithms 177 4.6 Eliminating Tail Recursion 178 4.7 Exercises 180 5 Array-Based Sequences 183 5.1 Python's Sequence Types 184 5.2 Low-Level Arrays 185 5.3 Dynamic Arrays and Amortization 192 5.4 Efficiency of Python's Sequence Types 202 5.5 Using Array-Based Sequences 210 5.6 Multidimensional Data Sets 219 5.7 Exercises 224 6 Stacks, Queues, and Deques 228 6.1 Stacks 229 6.2 Queues 239 6.3 Double-Ended Queues 247 6.4 Exercises 250 7 Linked Lists 255 7.1 Singly Linked Lists 256 7.2 Circularly Linked Lists 266 7.3 Doubly Linked Lists 270 7.4 The Positional List ADT 277 7.5 Sorting a Positional List 285 7.6 Case Study: Maintaining Access Frequencies 286 7.7 Link-Based vs Array-Based Sequences 292 7.8 Exercises 294 8 Trees 299 8.1 General Trees 300 8.2 Binary Trees 311 8.3 Implementing Trees 317 8.4 Tree Traversal Algorithms 328 8.5 Case Study: An Expression Tree 348 8.6 Exercises 352 9 Priority Queues 362 9.1 The Priority Queue Abstract Data Type 363 9.2 Implementing a Priority Queue 365 9.3 Heaps 370 9.4 Sorting with a Priority Queue 385 9.5 Adaptable Priority Queues 390 9.6 Exercises 395 10 Maps, Hash Tables, and Skip Lists 401 10.1 Maps and Dictionaries 402 10.2 Hash Tables 410 10.3 Sorted Maps 427 10.4 Skip Lists 437 10.5 Sets, Multisets, and Multimaps 446 10.6 Exercises 452 11 Search Trees 459 11.1 Binary Search Trees 460 11.2 Balanced Search Trees 475 11.2.1 Python Framework for Balancing Search Trees 478 11.3 AVL Trees 481 11.4 Splay Trees 490 11.5 (2,4) Trees 502 11.6 Red-Black Trees 512 11.7 Exercises 528 12 Sorting and Selection 536 12.1 Why Study Sorting Algorithms? 537 12.2 Merge-Sort 538 12.3 Quick-Sort 550 12.4 Studying Sorting through an Algorithmic Lens 562 12.5 Comparing Sorting Algorithms567 12.6 Python's Built-In Sorting Functions 569 12.7 Selection 571 12.8 Exercises 574 13 Text Processing 581 13.1 Abundance of Digitized Text 582 13.2 Pattern-Matching Algorithms 584 13.3 Dynamic Programming 594 13.4 Text Compression and the Greedy Method 601 13.5 Tries 604 13.6 Exercises 613 14 Graph Algorithms 619 14.1 Graphs 620 14.2 Data Structures for Graphs627 14.3 Graph Traversals 638 14.4 Transitive Closure 651 14.5 Directed Acyclic Graphs 655 14.6 Shortest Paths 659 14.7 Minimum Spanning Trees 670 14.8 Exercises 686 15 Memory Management and B-Trees 697 15.1 Memory Management 698 15.2 Memory Hierarchies and Caching 705 15.3 External Searching and B-Trees 711 15.4 External-Memory Sorting 715 15.5 Exercises 717 A Character Strings in Python 721 B Useful Mathematical Facts 725 Bibliography 732 Index 737

Back