Hetland Magnus Lie. Python Algorithms: Mastering Basic Algorithms in the Python Language [Code Files]

Apress, 2010. — 337 p. — ISBN13: 978-1-4302-3237-7.Code files only!
This book is a marriage of three of my passions: algorithms, Python programming, and explaining things. To me, all three of these are about aesthetics—finding just the right way of doing something, looking until you uncover a hint of elegance, and then polishing that until it shines. Or at least until it is a bit shinier. Of course, when there’s a lot of material to cover, you may not get to polish things quite as much as you want. Luckily, though, most of the contents in this book is prepolished, because I’m writing about really beautiful algorithms and proofs, as well as one of the cutest programming languages out there. As for the third part, I’ve tried hard to find explanations that will make things seem as obvious as possible.
Even so, I’m sure I have failed in many ways, and if you have suggestions for improving the book, I’d be happy to hear from you. Who knows, maybe some of your ideas could make it into a future edition? For now, though, I hope you have fun with what’s here and that you take any newfound insight and run with it. If you can, use it to make the world a more awesome place, in whatever way seems right.Consider the following problem. You are to visit all the cities, towns, and villages of, say, Sweden and then return to your starting point. This might take a while (there are 24 978 locations to visit, after all), so you want to minimize your route. You plan on visiting each location exactly once, following the shortest route possible. As a programmer, you certainly don’t want to plot the route by hand. Rather, you try to write some code that will plan your trip for you. For some reason, however, you can’t seem to get it right. A straightforward program works well for a smaller number of towns and cities but seems to run forever on the actual problem, and improving the program turns out to be surprisingly hard. How come?Actually, in 2004, a team of five researchers1 found such a tour of Sweden, after a number of other research teams had tried and failed. The five-man team used cutting-edge software with lots of clever optimizations and tricks of the trade, running on a cluster of 96 Xeon 2.6GHz workstations. Their software ran from March 2003 until May 2004, before it finally printed out the optimal solution. Taking various interruptions into account, the team estimated that the total CPU time spent was about 85 years! Consider a similar problem: You want to get from Kashgar, in the westernmost regions of China, to Ningbo, on the east coast, following the shortest route possible. Now, China has 3 583 715 km of roadways and 77 834 km of railways, with millions of intersections to consider and a virtually unfathomable number of possible routes to follow. It might seem that this problem is related to the previous one, yet this shortest path problem is one solved routinely, with no appreciable delay, by GPS software and online map services. If you give those two cities to your favorite map service, you should get the shortest route in mere moments. What’s going on here?You will learn more about both of these problems later in the book; the first one is called the traveling salesman (or salesrep) problem and is covered in Chapter 11, while so-called shortest path problems are primarily dealt with in Chapter 9. I also hope you will gain a rather deep insight into why one problem seems like such a hard nut to crack while the other admits several well-known, efficient solutions. More importantly, you will learn something about how to deal with algorithmic and computational problems in general, either solving them efficiently, using one of the several techniques and algorithms you encounter in this book, or showing that they are too hard and that approximate solutions may be all you can hope for. This chapter briefly describes what the book is about—what you can expect and what is expected of you. It also outlines the specific contents of the various chapters to come in case you want to skip around.The Basics
Counting
Induction and Recursion … and Reduction
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
A: Pedal to the Metal: Accelerating Python
B: List of Problems and Algorithms
C: Graph Terminology
D: Hints for Exercises