Phyton Data Structures and Algorithms with Python

[dEEpEst]

Data Structures and Algorithms with Python​

Contents
1 Python Programming 101 .............................. 1
1.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Creating Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Calling Methods on Objects . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Implementing a Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Operator Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Importing Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Indentation in Python Programs . . . . . . . . . . . . . . . . . . . . . 11
1.8 The Main Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.9 Reading from a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.10 Reading Multi-line Records from a File . . . . . . . . . . . . . . . . 16
1.11 A Container Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.12 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.13 The Accumulator Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.14 Implementing a GUI with Tkinter . . . . . . . . . . . . . . . . . . . . 24
1.15 XML Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.16 Reading XML Files. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.17 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.18 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.19 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2 Computer Architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3 Accessing Elements in a Python List . . . . . . . . . . . . . . . . . . 44
2.4 Big-Oh Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.5 The PyList Append Operation . . . . . . . . . . . . . . . . . . . . . . 50
2.6 A Proof by Induction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
xi
2.7 Making the PyList Append Efficient . . . . . . . . . . . . . . . . . . 53
2.8 Commonly Occurring Computational Complexities . . . . . . . . 55
2.9 More Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.10 Amortized Complexity. . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.11 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.12 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.13 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3 Recursion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.3 The Run-Time Stack and the Heap . . . . . . . . . . . . . . . . . . . 72
3.4 Writing a Recursive Function . . . . . . . . . . . . . . . . . . . . . . . 75
3.5 Tracing the Execution of a Recursive Function . . . . . . . . . . . 78
3.6 Recursion in Computer Graphics. . . . . . . . . . . . . . . . . . . . . 82
3.7 Recursion on Lists and Strings . . . . . . . . . . . . . . . . . . . . . . 83
3.8 Using Type Reflection. . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.9 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.10 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.11 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4 Sequences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.2 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.3 Cloning Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.4 Item Ordering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.5 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.6 Merge Sort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.7 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.8 Two-Dimensional Sequences . . . . . . . . . . . . . . . . . . . . . . . 112
4.9 The Minimax Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.10 Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.11 Stacks and Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.12 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.13 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.14 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5 Sets and Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2 Playing Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
5.3 Sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
5.4 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
5.5 The HashSet Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
5.6 Solving Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
xii Contents
5.7 Maps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.8 Memoization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
5.9 Correlating Two Sources of Information . . . . . . . . . . . . . . . 158
5.10 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5.11 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5.12 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
6 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.2 Abstract Syntax Trees and Expressions . . . . . . . . . . . . . . . . 164
6.3 Prefix and Postfix Expressions . . . . . . . . . . . . . . . . . . . . . . 166
6.4 Parsing Prefix Expressions . . . . . . . . . . . . . . . . . . . . . . . . . 167
6.5 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
6.6 Search Spaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
6.7 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
6.8 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
6.9 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
7 Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.2 Graph Notation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.3 Searching a Graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
7.4 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
7.5 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
7.6 Graph Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
7.7 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
7.8 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
7.9 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
8 Membership Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
8.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
8.2 Bloom Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
8.3 The Trie Datatype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
8.4 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
8.5 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
8.6 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
9 Heaps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
9.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
9.2 Key Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
9.3 Building a Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
9.4 The Heapsort Algorithm Version 1 . . . . . . . . . . . . . . . . . . . 219
9.5 Analysis of Version 1 Phase I. . . . . . . . . . . . . . . . . . . . . . . 221
Contents xiii
9.6 Phase II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
9.7 Analysis of Phase II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
9.8 The Heapsort Algorithm Version 2 . . . . . . . . . . . . . . . . . . . 229
9.9 Analysis of Heapsort Version 2 . . . . . . . . . . . . . . . . . . . . . 232
9.10 Comparison to Other Sorting Algorithms . . . . . . . . . . . . . . . 233
9.11 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
9.12 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
9.13 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
10 Balanced Binary Search Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . 237
10.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
10.2 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
10.3 AVL Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10.4 Splay Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
10.5 Iterative Splaying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
10.6 Recursive Splaying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
10.7 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
10.8 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
10.9 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
10.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
11 B-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
11.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
11.2 Relational Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
11.3 B-Tree Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
11.4 The Advantages of B-Trees . . . . . . . . . . . . . . . . . . . . . . . . 272
11.5 B-Tree Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
11.6 B-Tree Insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
11.7 B-Tree Delete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
11.8 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
11.9 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
11.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
12 Heuristic Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
12.1 Chapter Goals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
12.2 Depth First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
12.3 Breadth First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
12.4 Hill Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
12.5 Best First Search. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
12.6 A* Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
12.7 Minimax Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
12.8 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
12.9 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
12.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
xiv Contents
13 Appendix A: Integer Operators. . . . . . . . . . . . . . . . . . . . . . . . . . 299
14 Appendix B: Float Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
15 Appendix C: String Operators and Methods . . . . . . . . . . . . . . . . 303
16 Appendix D: List Operators and Methods . . . . . . . . . . . . . . . . . . 307
17 Appendix E: Dictionary Operators and Methods . . . . . . . . . . . . . 309
18 Appendix F: Turtle Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
19 Appendix G: TurtleScreen Methods. . . . . . . . . . . . . . . . . . . . . . . 323
20 Appendix H: Complete Programs . . . . . . . . . . . . . . . . . . . . . . . . 331
20.1 The Draw Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
20.2 The Scope Program. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
20.3 The Sort Animation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
20.4 The PlotData Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
20.5 The Tic Tac Toe Application . . . . . . . . . . . . . . . . . . . . . . . 348
20.6 The Connect Four Front-End . . . . . . . . . . . . . . . . . . . . . . . 353
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .361

Download:​

To see this hidden content, you must like this content.

​