Data Structures and Algorithms in Python

Michael Goodrich, PhD in Computer Science from Purdue University, 1987; Chancellor's Professor of Computer Science at University of California, Irvine; co-author (with Tamassia) of three other Wiley textbooks and a new computer security text, Addison Wesley, 2011. Roberto Tamassia, PhD in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign, 1988; Plastech Professor of Computer Science and Chair of the CS Dept at Brown University; co-author with Goodrich, see texts above. Michael Goldwasser, PhD in Computer Science from Stanford University, 1997; Associate Professor and Director of CS at St. Louis University; author of Object-Oriented Programming in Python, Pearson, 2008.

• Preface v1 Python Primer 11.1 Python Overview 21.2 Objects in Python 41.3 Expressions, Operators, and Precedence 121.4 Control Flow 181.5 Functions 231.6 Simple Input and Output 301.7 Exception Handling 331.8 Iterators and Generators 391.9 Additional Python Conveniences 421.10 Scopes and Namespaces 461.11 Modules and the Import Statement 481.12 Exercises 512 Object-Oriented Programming 562.1 Goals, Principles, and Patterns 572.2 Software Development 622.3 Class Definitions 692.4 Inheritance 822.5 Namespaces and Object-Orientation 962.6 Shallow and Deep Copying1012.7 Exercises 1033 Algorithm Analysis 1093.1 Experimental Studies 1113.1.1 Moving Beyond Experimental Analysis 1133.2 The Seven Functions Used in This Book 1153.3 Asymptotic Analysis 1233.4 Simple Justification Techniques 1373.5 Exercises 1414 Recursion 1484.1 Illustrative Examples 1504.2 Analyzing Recursive Algorithms 1614.3 Recursion Run Amok 1654.4 Further Examples of Recursion 1694.5 Designing Recursive Algorithms 1774.6 Eliminating Tail Recursion 1784.7 Exercises 1805 Array-Based Sequences 1835.1 Python’s Sequence Types 1845.2 Low-Level Arrays 1855.3 Dynamic Arrays and Amortization 1925.4 Efficiency of Python's Sequence Types 2025.5 Using Array-Based Sequences 2105.6 Multidimensional Data Sets 2195.7 Exercises 2246 Stacks, Queues, and Deques 2286.1 Stacks 2296.2 Queues 2396.3 Double-Ended Queues 2476.4 Exercises 2507 Linked Lists 2557.1 Singly Linked Lists 2567.2 Circularly Linked Lists 2667.3 Doubly Linked Lists 2707.4 The Positional List ADT 2777.5 Sorting a Positional List 2857.6 Case Study: Maintaining Access Frequencies 2867.7 Link-Based vs Array-Based Sequences 2927.8 Exercises 2948 Trees 2998.1 General Trees 3008.2 Binary Trees 3118.3 Implementing Trees 3178.4 Tree Traversal Algorithms 3288.5 Case Study: An Expression Tree 3488.6 Exercises 3529 Priority Queues 3629.1 The Priority Queue Abstract Data Type 3639.2 Implementing a Priority Queue 3659.3 Heaps 3709.4 Sorting with a Priority Queue 3859.5 Adaptable Priority Queues 3909.6 Exercises 39510 Maps, Hash Tables, and Skip Lists 40110.1 Maps and Dictionaries 40210.2 Hash Tables 41010.3 Sorted Maps 42710.4 Skip Lists 43710.5 Sets, Multisets, and Multimaps 44610.6 Exercises 45211 Search Trees 45911.1 Binary Search Trees 46011.2 Balanced Search Trees 47511.2.1 Python Framework for Balancing Search Trees 47811.3 AVL Trees 48111.4 Splay Trees 49011.5 (2,4) Trees 50211.6 Red-Black Trees 51211.7 Exercises 52812 Sorting and Selection 53612.1 Why Study Sorting Algorithms? 53712.2 Merge-Sort 53812.3 Quick-Sort 55012.4 Studying Sorting through an Algorithmic Lens 56212.5 Comparing Sorting Algorithms56712.6 Python's Built-In Sorting Functions 56912.7 Selection 57112.8 Exercises 57413 Text Processing 58113.1 Abundance of Digitized Text 58213.2 Pattern-Matching Algorithms 58413.3 Dynamic Programming 59413.4 Text Compression and the Greedy Method 60113.5 Tries 60413.6 Exercises 61314 Graph Algorithms 61914.1 Graphs 62014.2 Data Structures for Graphs62714.3 Graph Traversals 63814.4 Transitive Closure 65114.5 Directed Acyclic Graphs 65514.6 Shortest Paths 65914.7 Minimum Spanning Trees 67014.8 Exercises 68615 Memory Management and B-Trees 69715.1 Memory Management 69815.2 Memory Hierarchies and Caching 70515.3 External Searching and B-Trees 71115.4 External-Memory Sorting 71515.5 Exercises 717A Character Strings in Python 721B Useful Mathematical Facts 725Bibliography 732Index 737