Python Algorithms: Mastering Basic Algorithms in the Python Language

Prelim......Page 1
Contents at a Glance......Page 7
Contents......Page 8
About the Author......Page 15
About the Technical Reviewer......Page 16
Acknowledgments......Page 17
Preface......Page 18
Introduction......Page 19
 What’s All This, Then?......Page 20
 Why Are You Here?......Page 21
 Some Prerequisites......Page 22
 What’s in This Book......Page 23
 If You’re Curious …......Page 24
 References......Page 25
 Some Core Ideas in Computing......Page 27
 Asymptotic Notation......Page 28
  It’s Greek to Me!......Page 30
  Rules of the Road......Page 32
  Taking the Asymptotics for a Spin......Page 34
  Three Important Cases......Page 37
  Empirical Evaluation of Algorithms......Page 38
 Implementing Graphs and Trees......Page 41
  Adjacency Lists and the Like......Page 43
  Adjacency Matrices......Page 47
  Implementing Trees......Page 50
  A Multitude of Representations......Page 53
 Beware of Black Boxes......Page 54
  Hidden Squares......Page 55
  The Trouble with Floats......Page 56
 Summary......Page 58
 If You’re Curious …......Page 59
 Exercises......Page 60
 References......Page 61
 The Skinny on Sums......Page 63
  Working with Sums......Page 64
  Shaking Hands......Page 65
  The Hare and the Tortoise......Page 67
 Subsets, Permutations, and Combinations......Page 71
 Recursion and Recurrences......Page 74
  Doing It by Hand......Page 75
  A Few Important Examples......Page 76
  Guessing and Checking......Page 80
  The Master Theorem: A Cookie-Cutter Solution......Page 82
 So What Was All That About?......Page 85
 Summary......Page 86
 Exercises......Page 87
 References......Page 88
Induction and Recursion … and Reduction......Page 89
 Oh, That’s Easy!......Page 90
 One, Two, Many......Page 92
 Mirror, Mirror......Page 94
  Finding a Maximum Permutation......Page 99
  The Celebrity Problem......Page 103
  Topological Sorting......Page 105
 Stronger Assumptions......Page 109
 Invariants and Correctness......Page 110
 Relaxation and Gradual Improvement......Page 111
 Reduction + Contraposition = Hardness Proof......Page 112
 Problem Solving Advice......Page 113
 Summary......Page 114
 Exercises......Page 115
 References......Page 117
Traversal: The Skeleton Key of Algorithmics......Page 119
 A Walk in the Park......Page 125
  No Cycles Allowed......Page 126
  How to Stop Walking in Circles......Page 127
 Go Deep!......Page 128
  Depth-First Timestamps and Topological Sorting (Again)......Page 130
 Infinite Mazes and Shortest (Unweighted) Paths......Page 132
 Strongly Connected Components......Page 136
 Summary......Page 139
 Exercises......Page 140
 References......Page 141
 Tree-Shaped Problems: All About the Balance......Page 143
 The Canonical D&C Algorithm......Page 146
 Searching by Halves......Page 147
  Traversing Search Trees … with Pruning......Page 148
  Selection......Page 151
 Sorting by Halves......Page 153
  How Fast Can We Sort?......Page 155
  Closest Pair......Page 156
  Convex Hull......Page 158
  Greatest Slice......Page 160
 Tree Balance … and Balancing......Page 161
 Summary......Page 166
 Exercises......Page 167
 References......Page 168
 Staying Safe, Step by Step......Page 169
  Fractional Knapsack......Page 173
 Huffman’s Algorithm......Page 174
  The Algorithm......Page 176
  The First Greedy Choice......Page 177
  Optimal Merging......Page 178
 Minimum spanning trees......Page 179
  The Shortest Edge......Page 180
  What About the Rest?......Page 181
  Kruskal’s Algorithm......Page 182
  Prim’s Algorithm......Page 184
  Keeping Up with the Best......Page 186
  No Worse Than Perfect......Page 187
  Staying Safe......Page 188
 If You’re Curious …......Page 190
 Exercises......Page 191
 References......Page 192
Tangled Dependencies and Memoization......Page 193
 Don’t Repeat Yourself......Page 194
 Shortest Paths in Directed Acyclic Graphs......Page 200
 Longest Increasing Subsequence......Page 202
 Sequence Comparison......Page 205
 The Knapsack Strikes Back......Page 208
 Binary Sequence Partitioning......Page 211
 If You’re Curious …......Page 214
 Exercises......Page 215
 References......Page 216
From A to B with Edsger and Friends......Page 217
 Propagating Knowledge......Page 218
 Relaxing like Crazy......Page 219
 Finding the Hidden DAG......Page 222
 All Against All......Page 224
 Far-Fetched Subproblems......Page 226
 Meeting in the Middle......Page 229
 Knowing Where You’re Going......Page 231
 Summary......Page 235
 Exercises......Page 236
 References......Page 237
Matchings, Cuts, and Flows......Page 239
 Bipartite Matching......Page 240
 Disjoint Paths......Page 243
 Maximum Flow......Page 245
 Minimum Cut......Page 249
 Cheapest Flow and the Assignment Problem......Page 250
 Some Applications......Page 252
 If You’re Curious …......Page 255
 Exercises......Page 256
 References......Page 257
 Reduction Redux......Page 259
 Not in Kansas Anymore?......Page 262
 Meanwhile, Back in Kansas …......Page 264
 But Where Do You Start? And Where Do You Go from There?......Page 267
 A .........Page 270
  Return of the Knapsack......Page 272
  Cliques and Colorings......Page 274
  Paths and Circuits......Page 276
 When the Going Gets Tough, the Smart Get Sloppy......Page 279
 Desperately Seeking Solutions......Page 281
 And the Moral of the Story Is …......Page 283
 Exercises......Page 285
 References......Page 287
Pedal to the Metal: Accelerating Python......Page 289
 Problems......Page 293
 Algorithms and Data Structures......Page 296
Graph Terminology......Page 303
 Chapter 2......Page 309
 Chapter 4......Page 311
 Chapter 5......Page 314
 Chapter 6......Page 315
 Chapter 7......Page 317
 Chapter 8......Page 318
 Chapter 9......Page 319
 Chapter 10......Page 320
 Chapter 11......Page 321
 ¦ A......Page 325
 ¦ C......Page 326
 ¦ D......Page 327
 ¦ G......Page 328
 ¦ H......Page 329
 ¦......Page 330
 ¦ O......Page 331
 ¦ R......Page 332
 ¦ S......Page 333
 ¦ Z......Page 334