Data Structures and Algorithms Using Python

Cover......Page 1
Title Page......Page 3
Copyright......Page 4
Contents......Page 7
Preface......Page 15
 1.1 Introduction......Page 21
  1.1.1 Abstractions......Page 22
  1.1.2 Abstract Data Types......Page 23
  1.1.3 Data Structures......Page 25
  1.1.4 General Definitions......Page 26
  1.2.1 Defining the ADT......Page 27
  1.2.2 Using the ADT......Page 28
  1.2.3 Preconditions and Postconditions......Page 29
  1.2.4 Implementing the ADT......Page 30
 1.3 Bags......Page 34
  1.3.1 The Bag Abstract Data Type......Page 35
  1.3.2 Selecting a Data Structure......Page 37
  1.3.3 List-Based Implementation......Page 39
 1.4 Iterators......Page 40
  1.4.1 Designing an Iterator......Page 41
  1.4.2 Using Iterators......Page 42
  1.5.1 Designing a Solution......Page 43
  1.5.2 Implementation......Page 46
 Exercises......Page 48
 Programming Projects......Page 49
 2.1 The Array Structure......Page 53
  2.1.2 The Array Abstract Data Type......Page 54
  2.1.3 Implementing the Array......Page 56
  2.2.1 Creating a Python List......Page 61
  2.2.2 Appending Items......Page 62
  2.2.4 Inserting Items......Page 64
  2.2.5 List Slice......Page 65
  2.3.1 The Array2D Abstract Data Type......Page 67
  2.3.2 Implementing the 2-D Array......Page 69
 2.4 The Matrix Abstract Data Type......Page 72
  2.4.1 Matrix Operations......Page 73
  2.4.2 Implementing the Matrix......Page 75
  2.5.1 Rules of the Game......Page 77
  2.5.2 Designing a Solution......Page 79
  2.5.3 Implementation......Page 81
 Exercises......Page 84
 Programming Projects......Page 85
 3.1 Sets......Page 89
  3.1.1 The Set Abstract Data Type......Page 90
  3.1.3 List-Based Implementation......Page 92
 3.2 Maps......Page 95
  3.2.1 The Map Abstract Data Type......Page 96
  3.2.2 List-Based Implementation......Page 97
 3.3 Multi-Dimensional Arrays......Page 100
  3.3.2 Data Organization......Page 101
  3.3.3 Variable-Length Arguments......Page 105
  3.3.4 Implementing the MultiArray......Page 106
 3.4 Application: Sales Reports......Page 109
 Exercises......Page 115
 Programming Projects......Page 116
 4.1 Complexity Analysis......Page 117
  4.1.1 Big-O Notation......Page 119
  4.1.2 Evaluating Python Code......Page 124
 4.2 Evaluating the Python List......Page 128
 4.3 Amortized Cost......Page 131
 4.4 Evaluating the Set ADT......Page 133
  4.5.1 List-Based Implementation......Page 135
  4.5.2 Efficiency Analysis......Page 140
 Exercises......Page 141
 Programming Projects......Page 142
 5.1 Searching......Page 145
  5.1.1 The Linear Search......Page 146
  5.1.2 The Binary Search......Page 148
 5.2 Sorting......Page 151
  5.2.1 Bubble Sort......Page 152
  5.2.2 Selection Sort......Page 156
  5.2.3 Insertion Sort......Page 158
  5.3.1 Maintaining a Sorted List......Page 162
  5.3.2 Merging Sorted Lists......Page 163
  5.4.1 A Sorted List Implementation......Page 167
 Exercises......Page 172
 Programming Projects......Page 173
Chapter 6: Linked Structures......Page 175
 6.1 Introduction......Page 176
  6.2.1 Traversing the Nodes......Page 179
  6.2.2 Searching for a Node......Page 181
  6.2.3 Prepending Nodes......Page 182
  6.2.4 Removing Nodes......Page 183
  6.3.1 A Linked List Implementation......Page 185
  6.3.2 Comparing Implementations......Page 187
  6.3.3 Linked List Iterators......Page 188
  6.4.1 Using a Tail Reference......Page 189
  6.4.2 The Sorted Linked List......Page 191
 6.5 The Sparse Matrix Revisited......Page 194
  6.5.1 An Array of Linked Lists Implementation......Page 195
  6.5.2 Comparing the Implementations......Page 198
  6.6.1 Polynomial Operations......Page 199
  6.6.3 Implementation......Page 201
 Exercises......Page 209
 Programming Projects......Page 210
 7.1 The Stack ADT......Page 213
  7.2.1 Using a Python List......Page 215
  7.2.2 Using a Linked List......Page 216
 7.3 Stack Applications......Page 218
  7.3.1 Balanced Delimiters......Page 219
  7.3.2 Evaluating Postfix Expressions......Page 222
 7.4 Application: Solving a Maze......Page 226
  7.4.1 Backtracking......Page 227
  7.4.2 Designing a Solution......Page 228
  7.4.3 The Maze ADT......Page 231
  7.4.4 Implementation......Page 234
 Exercises......Page 238
 Programming Projects......Page 239
 8.1 The Queue ADT......Page 241
  8.2.1 Using a Python List......Page 242
  8.2.2 Using a Circular Array......Page 244
  8.2.3 Using a Linked List......Page 248
  8.3.1 The Priority Queue ADT......Page 250
  8.3.2 Implementation: Unbounded Priority Queue......Page 252
  8.3.3 Implementation: Bounded Priority Queue......Page 255
  8.4.1 Airline Ticket Counter......Page 257
  8.4.2 Implementation......Page 259
 Exercises......Page 264
 Programming Projects......Page 266
  9.1.1 Organization......Page 267
  9.1.2 List Operations......Page 268
  9.2.1 Organization......Page 273
  9.2.2 List Operations......Page 274
  9.3.1 Multiple Chains......Page 279
  9.3.2 The Sparse Matrix......Page 280
 9.4 Complex Iterators......Page 282
  9.5.1 Typical Editor Operations......Page 283
  9.5.2 The Edit Buffer ADT......Page 286
  9.5.3 Implementation......Page 288
 Programming Projects......Page 295
 10.1 Recursive Functions......Page 297
 10.2 Properties of Recursion......Page 299
  10.2.1 Factorials......Page 300
  10.2.2 Recursive Call Trees......Page 301
 10.3 How Recursion Works......Page 303
  10.3.1 The Run Time Stack......Page 304
  10.3.2 Using a Software Stack......Page 306
  10.3.3 Tail Recursion......Page 309
  10.4.1 Recursive Binary Search......Page 310
  10.4.2 Towers of Hanoi......Page 312
  10.4.3 Exponential Operation......Page 316
  10.4.4 Playing Tic-Tac-Toe......Page 317
 10.5 Application: The Eight-Queens Problem......Page 319
  10.5.1 Solving for Four-Queens......Page 321
  10.5.2 Designing a Solution......Page 323
 Exercises......Page 327
 Programming Projects......Page 328
 11.1 Introduction......Page 329
 11.2 Hashing......Page 331
  11.2.1 Linear Probing......Page 332
  11.2.2 Clustering......Page 335
  11.2.3 Rehashing......Page 338
  11.2.4 Efficiency Analysis......Page 340
 11.3 Separate Chaining......Page 341
 11.4 Hash Functions......Page 343
 11.5 The HashMap Abstract Data Type......Page 345
  11.6.1 The Histogram Abstract Data Type......Page 350
  11.6.2 The Color Histogram......Page 354
 Exercises......Page 357
 Programming Projects......Page 358
 12.1 Merge Sort......Page 359
  12.1.2 Basic Implementation......Page 360
  12.1.3 Improved Implementation......Page 362
  12.1.4 Efficiency Analysis......Page 365
 12.2 Quick Sort......Page 367
  12.2.1 Algorithm Description......Page 368
  12.2.2 Implementation......Page 369
 12.3 How Fast Can We Sort?......Page 373
  12.4.1 Algorithm Description......Page 374
  12.4.2 Basic Implementation......Page 376
 12.5 Sorting Linked Lists......Page 378
  12.5.1 Insertion Sort......Page 379
  12.5.2 Merge Sort......Page 382
 Exercises......Page 387
 Programming Projects......Page 388
 13.1 The Tree Structure......Page 389
  13.2.1 Properties......Page 393
  13.2.2 Implementation......Page 395
  13.2.3 Tree Traversals......Page 396
 13.3 Expression Trees......Page 400
  13.3.1 Expression Tree Abstract Data Type......Page 402
  13.3.2 String Representation......Page 403
  13.3.3 Tree Evaluation......Page 404
  13.3.4 Tree Construction......Page 406
 13.4 Heaps......Page 410
  13.4.1 Definition......Page 411
  13.4.2 Implementation......Page 415
  13.4.3 The Priority Queue Revisited......Page 418
  13.5.2 Sorting In Place......Page 420
 13.6 Application: Morse Code......Page 424
  13.6.1 Decision Trees......Page 425
  13.6.2 The ADT Definition......Page 426
 Exercises......Page 427
 Programming Projects......Page 430
Chapter 14: Search Trees......Page 431
 14.1 The Binary Search Tree......Page 432
  14.1.1 Searching......Page 433
  14.1.2 Min and Max Values......Page 435
  14.1.3 Insertions......Page 437
  14.1.4 Deletions......Page 440
  14.1.5 Efficiency of Binary Search Trees......Page 445
 14.2 Search Tree Iterators......Page 447
 14.3 AVL Trees......Page 448
  14.3.1 Insertions......Page 450
  14.3.2 Deletions......Page 453
  14.3.3 Implementation......Page 455
 14.4 The 2-3 Tree......Page 460
  14.4.1 Searching......Page 462
  14.4.2 Insertions......Page 463
  14.4.3 Efficiency of the 2-3 Tree......Page 469
 Exercises......Page 471
 Programming Projects......Page 472
 A.1 The Python Interpreter......Page 473
 A.2 The Basics of Python......Page 474
  A.2.1 Primitive Types......Page 475
  A.2.2 Statements......Page 476
  A.2.3 Variables......Page 477
  A.2.4 Arithmetic Operators......Page 478
  A.2.5 Logical Expressions......Page 479
  A.2.6 Using Functions and Methods......Page 481
  A.2.7 Standard Library......Page 482
  A.3.1 Standard Input......Page 483
  A.3.2 Standard Output......Page 484
  A.4.1 Selection Constructs......Page 487
  A.4.2 Repetition Constructs......Page 489
  A.5.1 Strings......Page 492
  A.5.2 Lists......Page 493
  A.5.4 Dictionaries......Page 495
  A.6.1 File Access......Page 497
  A.6.2 Writing to Files......Page 498
  A.6.3 Reading from Files......Page 499
  A.7.1 The Function Definition......Page 500
  A.7.3 Main Routine......Page 503
 B.1 Structured Programs......Page 505
 B.2 Namespaces......Page 506
 C.1 Catching Exceptions......Page 509
 C.2 Raising Exceptions......Page 510
 C.4 Assertions......Page 511
 D.1 The Class Definition......Page 513
  D.1.1 Constructors......Page 514
  D.1.2 Operations......Page 515
  D.1.3 Using Modules......Page 517
  D.1.4 Hiding Attributes......Page 518
 D.2 Overloading Operators......Page 520
 D.3 Inheritance......Page 522
  D.3.1 Deriving Child Classes......Page 523
  D.3.2 Creating Class Instances......Page 524
  D.3.3 Invoking Methods......Page 525
 D.4 Polymorphism......Page 527
Bibliography......Page 529
Index......Page 531