Python Algorithms: Mastering Basic Algorithms in the Python Language (Expert's Voice in Open Source)

Python Algorithms explains the Python approach to algorithm analysis and design. Written by Magnus Lie Hetland, author of Beginning Python, this book is sharply focused on classical algorithms, but it also gives a solid understanding of fundamental algorithmic problem-solving techniques. The book deals with some of the most important and challenging areas of programming and computer science, but in a highly pedagogic and readable manner. The book covers both algorithmic theory and programming practice, demonstrating how theory is reflected in real Python programs. Well-known algorithms and data structures that are built into the Python language are explained, and the user is shown how to implement and evaluate others himself. What you’ll learn Transform new problems to well-known algorithmic problems with efficient solutions, or show that the problems belong to classes of problems thought not to be efficiently solvable. Analyze algorithms and Python programs both using mathematical tools and basic experiments and benchmarks. Prove correctness, optimality, or bounds on approximation error for Python programs and their underlying algorithms. Understand several classical algorithms and data structures in depth, and be able to implement these efficiently in Python. Design and implement new algorithms for new problems, using time-tested design principles and techniques. Speed up implementations, using a plethora of tools for high-performance computing in Python. Who this book is for The book is intended for Python programmers who need to learn about algorithmic problem-solving, or who need a refresher. Students of computer science, or similar programming-related topics, such as bioinformatics, may also find the book to be quite useful. Table of Contents Introduction The Basics Counting 101 Induction and Recursion ... and Reduction Traversal: The Skeleton Key of Algorithmics Divide, Combine, and Conquer Greed Is Good? Prove It! Tangled Dependencies and Memoization From A to B with Edsger and Friends Matchings, Cuts, and Flows Hard Problems and (Limited) Sloppiness 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

Python Algorithms explains the Python approach to algorithm analysis and design. Written by Magnus Lie Hetland, author of Beginning Python,this bookis sharply focused on classical algorithms, but it also gives a solid understanding of fundamental algorithmic problem-solving techniques.

• The book deals with some of the most important and challenging areas of programming and computer science, but in a highly pedagogic and readable manner.
• The book covers both algorithmic theory and programming practice, demonstrating how theory is reflected in real Python programs.
• Well-known algorithms and data structures that are built into the Python language are explained, and the user is shown how to implement and evaluate others himself.

What you’ll learn

• Transform new problems to well-known algorithmic problems with efficient solutions, or show that the problems belong to classes of problems thought not to be efficiently solvable.
• Analyze algorithms and Python programs both using mathematical tools and basic experiments and benchmarks.
• Prove correctness, optimality, or bounds on approximation error for Python programs and their underlying algorithms.
• Understand several classical algorithms and data structures in depth, and be able to implement these efficiently in Python.
• Design and implement new algorithms for new problems, using time-tested design principles and techniques.
• Speed up implementations, using a plethora of tools for high-performance computing in Python.

Who this book is for

The book is intended for Python programmers who need to learn about algorithmic problem-solving, or who need a refresher. Students of computer science, or similar programming-related topics, such as bioinformatics, may also find the book to be quite useful.

Table of Contents

1. Introduction
2. The Basics
3. Counting 101
4. Induction and Recursion ... and Reduction
5. Traversal: The Skeleton Key of Algorithmics
6. Divide, Combine, and Conquer
7. Greed Is Good? Prove It!
8. Tangled Dependencies and Memoization
9. From A to B with Edsger and Friends
10. Matchings, Cuts, and Flows
11. Hard Problems and (Limited) Sloppiness