دانلود کتاب Data Structures and Algorithms with Python

فهرست مطالب :

Preface......Page 6
For Teachers......Page 8
Credits......Page 10
Contents......Page 11
1 Python Programming 101......Page 16
1.2.1 Literal Values......Page 18
1.2.2 Non-literal Object Creation......Page 19
1.3 Calling Methods on Objects......Page 20
1.4.1 Creating Objects and Calling Methods......Page 21
1.4.2 The Dog Class......Page 22
1.5.1 The Dog Class with Overloaded Addition......Page 23
1.6 Importing Modules......Page 25
1.7 Indentation in Python Programs......Page 26
1.8.1 Python Program Structure......Page 27
1.9.1 A Text File with Single Line Records......Page 28
1.9.2 Reading and Processing Single Line Records......Page 29
1.9.3 Pattern for Reading Single Line Records from a File......Page 30
1.10.1 A Text File with Multiple Line Records......Page 31
1.10.2 Reading and Processing Multi-line Records......Page 33
1.10.3 Pattern for Reading Multi-line Records from a File......Page 34
1.12 Polymorphism......Page 35
1.12.1 Graphics Command Classes......Page 36
1.13.2 A Graphics Program......Page 37
1.14 Implementing a GUI with Tkinter......Page 39
1.14.1 A GUI Drawing Application......Page 42
1.15 XML Files......Page 47
1.15.1 The Truck XML File......Page 48
1.15.2 The GoToCommand with XML Creation Code......Page 49
1.16 Reading XML Files......Page 50
1.16.1 Using an XML Parser......Page 51
1.17 Chapter Summary......Page 52
1.18 Review Questions......Page 53
1.19 Programming Problems......Page 54
2.1 Chapter Goals......Page 56
2.2.1 Running a Program......Page 57
2.3.1 List Access Timing......Page 59
2.3.2 A Plot XML Sample......Page 61
2.4 Big-Oh Notation......Page 63
2.5 The PyList Append Operation......Page 65
2.6 A Proof by Induction......Page 66
2.7 Making the PyList Append Efficient......Page 68
2.8 Commonly Occurring Computational Complexities......Page 70
2.9 More Asymptotic Notation......Page 71
2.9.1 Big-Oh Asymptotic Upper Bound......Page 72
2.10 Amortized Complexity......Page 73
2.10.2 Proof of Append Complexity......Page 75
2.11 Chapter Summary......Page 77
2.13 Programming Problems......Page 78
3 Recursion......Page 81
3.1 Chapter Goals......Page 82
3.2.1 Local Scope......Page 83
3.2.2 Enclosing Scope......Page 84
3.2.3 Global Scope......Page 85
3.3 The Run-Time Stack and the Heap......Page 86
3.4 Writing a Recursive Function......Page 89
3.4.1 Sum of Integers......Page 90
3.4.2 Recursive Sum of Integers......Page 91
3.5 Tracing the Execution of a Recursive Function......Page 92
3.6.1 Recursive Spiral......Page 96
3.7.1 List Recursion......Page 97
3.7.2 Reversing a List......Page 98
3.7.4 Another Version of Reverse......Page 99
3.8.1 Reflection Reverse......Page 100
3.9 Chapter Summary......Page 101
3.11 Programming Problems......Page 102
4.1 Chapter Goals......Page 105
4.2 Lists......Page 106
4.2.2 The PyList Constructor......Page 107
4.2.3 PyList Get and Set......Page 108
4.2.5 PyList Append......Page 109
4.2.6 PyList Insert......Page 110
4.2.9 PyList Iteration......Page 111
4.2.12 PyList String Conversion......Page 112
4.3 Cloning Objects......Page 113
4.4.1 The Point Class......Page 114
4.4.2 Calling the Sort Method......Page 115
4.5 Selection Sort......Page 116
4.5.2 The Selection Sort Code......Page 117
4.6 Merge Sort......Page 119
4.6.1 The Merge Sort Code......Page 120
4.7 Quicksort......Page 123
4.7.1 The Quicksort Code......Page 124
4.8 Two-Dimensional Sequences......Page 126
4.8.1 The Board Class......Page 127
4.8.2 The X, O, and Dummy Classes......Page 129
4.9 The Minimax Algorithm......Page 130
4.10 Linked Lists......Page 131
4.10.1 The Node Class......Page 132
4.10.2 The LinkedList Constructor......Page 133
4.10.3 LinkedList Get and Set......Page 134
4.10.5 LinkedList Append......Page 135
4.10.7 Other Linked List Operations......Page 136
4.11 Stacks and Queues......Page 137
4.11.1 The Stack Class Code......Page 138
4.11.2 Infix Expression Evaluation......Page 141
4.11.3 Radix Sort......Page 143
4.11.4 The CharAt Function......Page 145
4.13 Review Questions......Page 149
4.14 Programming Problems......Page 150
5.1 Chapter Goals......Page 153
5.2 Playing Sudoku......Page 154
5.3 Sets......Page 156
5.4 Hashing......Page 158
5.5 The HashSet Class......Page 159
5.5.3 Collision Resolution......Page 160
5.5.4 HashSet Add Helper Function......Page 161
5.5.7 Deleting an Item......Page 162
5.5.10 Finding an Item......Page 163
5.5.14 HashSet Difference Update......Page 164
5.6 Solving Sudoku......Page 165
5.6.1 The Sudoku Reduce Function......Page 166
5.7 Maps......Page 167
5.7.2 HashSet Get Item......Page 168
5.7.3 The HashMap Class......Page 169
5.8 Memoization......Page 170
5.8.1 A Memoized Fibonacci Function......Page 171
5.9 Correlating Two Sources of Information......Page 172
5.11 Review Questions......Page 173
5.12 Programming Problems......Page 174
6.1 Chapter Goals......Page 176
6.2 Abstract Syntax Trees and Expressions......Page 177
6.2.1 Constructing ASTs......Page 178
6.3.1 AST Tree Traversal......Page 179
6.4 Parsing Prefix Expressions......Page 180
6.4.2 A Prefix Expression Parser......Page 181
6.4.3 The Postfix Expression Grammar......Page 182
6.5.1 The BinarySearchTree Class......Page 183
6.6 Search Spaces......Page 189
6.6.2 Sudoku Depth-First Search......Page 190
6.6.3 Calling Sudoku\'s Solve Function......Page 191
6.8 Review Questions......Page 192
6.9 Programming Problems......Page 193
7.1 Chapter Goals......Page 197
7.2 Graph Notation......Page 198
7.3 Searching a Graph......Page 200
7.3.1 Iterative Depth First Search of a Graph......Page 201
7.4 Kruskal\'s Algorithm......Page 202
7.4.2 Kruskal\'s Complexity Analysis......Page 206
7.4.3 The Partition Data Structure......Page 207
7.5 Dijkstra\'s Algorithm......Page 208
7.5.1 Dijkstra\'s Complexity Analysis......Page 210
7.6.1 A Graph XML File......Page 211
7.6.2 A Vertex Class......Page 212
7.7 Chapter Summary......Page 213
7.9 Programming Problems......Page 214
8.1 Chapter Goals......Page 217
8.2 Bloom Filters......Page 218
8.2.1 The Hashing Functions......Page 219
8.2.2 The Bloom Filter Size......Page 220
8.3 The Trie Datatype......Page 221
8.3.2 Inserting into a Trie......Page 223
8.3.4 Comparing Tries and Bloom Filters......Page 224
8.5 Review Questions......Page 225
8.6 Programming Problems......Page 226
9.2 Key Ideas......Page 227
9.3.1 The buildFrom Method......Page 229
9.4 The Heapsort Algorithm Version 1......Page 231
9.4.1 The addToHeap Method......Page 232
9.5 Analysis of Version 1 Phase I......Page 233
9.6.1 The siftDownFromTo Method......Page 237
9.7 Analysis of Phase II......Page 240
9.8 The Heapsort Algorithm Version 2......Page 241
9.9 Analysis of Heapsort Version 2......Page 244
9.10 Comparison to Other Sorting Algorithms......Page 245
9.11 Chapter Summary......Page 246
9.12 Review Questions......Page 247
9.13 Programming Problems......Page 248
10.1 Chapter Goals......Page 249
10.2.1 Binary Search Tree Insert......Page 250
10.3.1 Definitions......Page 251
10.3.3 AVLNode with Stored Balance......Page 252
10.3.4 AVL Tree Iterative Insert......Page 253
10.3.5 Rotations......Page 257
10.3.7 The Recursive Insert AVL Tree Class Declaration......Page 260
10.3.9 AVLNode with Stored Height......Page 261
10.4 Splay Trees......Page 262
10.4.1 Splay Rotations......Page 263
10.5 Iterative Splaying......Page 266
10.6 Recursive Splaying......Page 268
10.7 Performance Analysis......Page 269
10.8 Chapter Summary......Page 270
10.10 Programming Problems......Page 271
11.2 Relational Databases......Page 273
11.2.2 The FeedAttribType Table......Page 276
11.2.4 A Temporary Table......Page 277
11.2.5 Programming the Joining of Tables......Page 278
11.2.6 The readRecord Function......Page 280
11.2.7 Efficient Join......Page 281
11.3 B-Tree Organization......Page 282
11.4 The Advantages of B-Trees......Page 284
11.6 B-Tree Insert......Page 286
11.7 B-Tree Delete......Page 288
11.9 Review Questions......Page 291
11.10 Programming Problems......Page 292
12.1 Chapter Goals......Page 293
12.2.1 Iterative Depth First Search of a Graph......Page 294
12.2.3 DFS Example......Page 295
12.3.1 BFS Example......Page 297
12.4.1 Hill Climbing Example......Page 298
12.4.2 Closed Knight\'s Tour......Page 300
12.4.3 The N-Queens Problem......Page 301
12.5.1 Best First Example......Page 303
12.6.1 A* Example......Page 304
12.7 Minimax Revisited......Page 305
12.9 Review Questions......Page 307
12.10 Programming Problems......Page 308
13 Appendix A: Integer Operators......Page 310
14 Appendix B: Float Operators......Page 311
15 Appendix C: String Operators and Methods......Page 312
16 Appendix D: List Operators and Methods......Page 316
17 Appendix E: Dictionary Operators and Methods......Page 318
18 Appendix F: Turtle Methods......Page 320
19 Appendix G: TurtleScreen Methods......Page 331
20.1 The Draw Program......Page 339
20.2 The Scope Program......Page 346
20.3 The Sort Animation......Page 347
20.4 The PlotData Program......Page 354
20.5 The Tic Tac Toe Application......Page 356
20.6 The Connect Four Front-End......Page 361
Bibliography......Page 366
Index......Page 367