Data Structures and Algorithms in Python

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