Download
Introduction
What’s All This, Then?
This is a book about algorithmic problem solving for Python programmers. Just like books on, say, object-oriented patterns, the problems it deals with are of a general nature—as are the solutions. For an algorist, there is more to the job than simply implementing or executing an existing algorithm, however. You are expected to come up with new algorithms—new general solutions to hitherto unseen, general problems. In this book, you are going to learn principles for constructing such solutions.
This is not your typical algorithm book, though. Most of the authoritative books on the subject (such as Knuth’s classics or the industry-standard textbook by Cormen et al.) have a heavy formal and theoretical slant, even though some of them (such as the one by Kleinberg and Tardos) lean more in the direction of readability. Instead of trying to replace any of these excellent books, I’d like to supplement them. Building on my experience from teaching algorithms, I try to explain as clearly as possible how the algorithms work and what common principles underlie many of them. For a programmer, these explanations are probably enough. Chances are you’ll be able to understand why the algorithms are correct and how to adapt them to new problems you may come to face. If, however, you need the full depth of the more formalistic and encyclopedic textbooks, I hope the foundation you get in this book will help you understand the theorems and proofs you encounter there
There is another genre of algorithm books as well: the “(Data Structures and) Algorithms in blank” kind, where the blank is the author’s favorite programming language. There are quite a few of these (especially for blank = Java, it seems), but many of them focus on relatively basic data structures, to the detriment of the meatier stuff. This is understandable if the book is designed to be used in a basic course on data structures, for example, but for a Python programmer, learning about singly and doubly linked lists may not be all that exciting (although you will hear a bit about those in the next chapter). And even though techniques such as hashing are highly important, you get hash tables for free in the form of Python dictionaries; there’s no need to implement them from scratch. Instead, I focus on more high-level algorithms. Many important concepts that are available as black-box implementations either in the Python language itself or in the standard library (such as sorting, searching, and hashing) are explained more briefly, in special “Black Box” sidebars throughout the text.
There is, of course, another factor that separates this book from those in the “Algorithms in Java/C/C++/C#” genre, namely, that the blank is Python. This places the book one step closer to the language-independent books (such as those by Knuth,3 Cormen et al., and Kleinberg and Tardos, for example), which often use pseudocode, the kind of fake programming language that is designed to be readable rather than executable. One of Python’s distinguishing features is its readability; it is, more or less, executable pseudocode. Even if you’ve never programmed in Python, you could probably decipher the meaning of most basic Python programs. The code in this book is designed to be readable exactly in this fashion—you need not be a Python expert to understand the examples (although you might need to look up some built-in functions and the like). And if you want to pretend the examples are actually pseudocode, feel free to do so
What the book is about:
• Algorithm analysis, with a focus on asymptotic running time
• Basic principles of algorithm design
• How to represent commonly used data structures in Python
• How to implement well-known algorithms in Python What the book covers only briefly or partially: • Algorithms that are directly available in Python, either as part of the language or via the standard library
• Thorough and deep formalism (although the book has its share of proofs and proof-like explanations)
What the book isn’t about:
• Numerical or number-theoretical algorithms (except for some floating-point hints in Chapter 2)
• Parallel algorithms and multicore programming
As you can see, “implementing things in Python” is just part of the picture. The design principles and theoretical foundations are included in the hope that they’ll help you design your own algorithms and data structures
