Python Algorithms (eBook)

Magnus Lie Hetland is an experienced Python programmer, having used the language since the late 1990s. He is also an associate professor of algorithms at the Norwegian University of Science and Technology, having taught algorithms for the better part of a decade. Hetland is the author of Practical Python and Beginning Python, first and second editions, as well as several scientific papers.

Contents at a Glance 3
Contents 293
About the Author 300
About the Technical Reviewer 301
Acknowledgments 302
Preface 303
Chapter 1: Introduction 5
What’s All This, Then? 6
Why Are You Here? 7
Some Prerequisites 8
What’s in This Book 9
Summary 10
If You’re Curious … 10
Exercises 10
References 11
Chapter 2: The Basics 12
Some Core Ideas in Computing 12
Asymptotic Notation 13
It’s Greek to Me! 15
Rules of the Road 17
Taking the Asymptotics for a Spin 18
Three Important Cases 21
Empirical Evaluation of Algorithms 22
Implementing Graphs and Trees 25
Adjacency Lists and the Like 27
Adjacency Matrices 30
Implementing Trees 33
A Multitude of Representations 36
Beware of Black Boxes 37
Hidden Squares 38
The Trouble with Floats 39
Summary 41
If You’re Curious … 42
Exercises 42
References 43
Chapter 3: Counting 101 45
The Skinny on Sums 45
More Greek 46
Working with Sums 46
A Tale of Two Tournaments 47
Shaking Hands 47
The Hare and the Tortoise 49
Subsets, Permutations, and Combinations 52
Recursion and Recurrences 55
Doing It by Hand 55
A Few Important Examples 57
Guessing and Checking 60
The Master Theorem: A Cookie-Cutter Solution 62
So What Was All That About? 65
Summary 66
If You’re Curious ... 67
Exercises 67
References 68
Chapter 4: Induction and Recursion ... and Reduction 69
Oh, That’s Easy! 70
One, Two, Many 71
Mirror, Mirror 73
Designing with Induction (and Recursion) 77
Finding a Maximum Permutation 78
The Celebrity Problem 82
Topological Sorting 84
Stronger Assumptions 87
Invariants and Correctness 88
Relaxation and Gradual Improvement 89
Reduction + Contraposition = Hardness Proof 90
Problem Solving Advice 91
Summary 92
If You’re Curious ... 92
Exercises 93
References 94
Chapter 5: Traversal: The Skeleton Key of Algorithmics 95
A Walk in the Park 101
No Cycles Allowed 102
How to Stop Walking in Circles 103
Go Deep! 104
Depth-First Timestamps and Topological Sorting (Again) 106
Infinite Mazes and Shortest (Unweighted) Paths 108
Strongly Connected Components 111
Summary 114
If You’re Curious ... 114
Exercises 114
References 115
Chapter 6: Divide, Combine, and Conquer 116
Tree-Shaped Problems: All About the Balance 116
The Canonical D& C Algorithm
Searching by Halves 119
Traversing Search Trees ... with Pruning 121
Selection 124
Sorting by Halves 126
How Fast Can We Sort? 128
Three More Examples 128
Closest Pair 128
Convex Hull 130
Greatest Slice 131
Tree Balance ... and Balancing * 132
Summary 137
If You’re Curious ... 138
Exercises 138
References 139
Chapter 7: Greed Is Good? Prove It! 140
Staying Safe, Step by Step 140
The Knapsack Problem 144
Fractional Knapsack 144
Integer Knapsack 144
Huffman’s Algorithm 145
The Algorithm 146
The First Greedy Choice 148
Going the Rest of the Way 148
Optimal Merging 149
Minimum Spanning Trees 150
The Shortest Edge 150
What About the Rest? 152
Kruskal’s Algorithm 152
Prim’s Algorithm 154
Greed Works. But When? 156
Keeping Up with the Best 156
No Worse Than Perfect 158
Staying Safe 158
Summary 160
If You’re Curious … 161
Exercises 161
References 162
Chapter 8: Tangled Dependencies and Memoization 163
Don’t Repeat Yourself 164
Shortest Paths in Directed Acyclic Graphs 170
Longest Increasing Subsequence 172
Sequence Comparison 175
The Knapsack Strikes Back 178
Binary Sequence Partitioning 180
Summary 183
If You’re Curious … 183
Exercises 184
References 185
Chapter 9: From A to B with Edsger and Friends 186
Propagating Knowledge 187
Relaxing like Crazy 188
Finding the Hidden DAG 193
All Against All 196
Far-Fetched Subproblems 197
Meeting in the Middle 200
Knowing Where You’re Going 202
Summary 205
If You’re Curious ... 206
Exercises 206
References 207
Chapter 10:Matchings, Cuts, and Flows 208
Bipartite Matching 209
Disjoint Paths 211
Maximum Flow 214
Minimum Cut 217
Cheapest Flow and the Assignment Problem * 218
Some Applications 220
Summary 223
If You’re Curious … 223
Exercises 223
References 224
Chapter 11: Hard Problems and (Limited) Sloppiness 225
Reduction Redux 226
Not in Kansas Anymore? 228
Meanwhile, Back in Kansas … 230
But Where Do You Start? And Where Do You Go from There? 233
A Ménagerie of Monsters 237
Return of the Knapsack 237
Cliques and Colorings 238
Paths and Circuits 240
When the Going Gets Tough, the Smart Get Sloppy 243
Desperately Seeking Solutions 245
And the Moral of the Story Is … 247
Summary 248
If You’re Curious … 249
Exercises 249
References 250
Chapter 12:Pedal to the Metal: Accelerating Python 252
Chapter 13:List of Problems and Algorithms 256
Problems 256
Algorithms and Data Structures 259
Chapter 14:Graph Terminology 263
Chapter 15:Hints for Exercises 268
Chapter 1 268
Chapter 2 268
Chapter 3 270
Chapter 4 271
Chapter 5 273
Chapter 6 274
Chapter 7 275
Chapter 8 277
Chapter 9 278
Chapter 10 279
Chapter 11 280
Index 283