Apress Access

Python Algorithms

Mastering Basic Algorithms in the Python Language

By Magnus Lie Hetland

  • eBook Price: $38.99
Buy eBook Buy Print Book
Learn to implement classic algorithms and design new problem-solving algorithms using Python.

Full Description

  • Add to Wishlist
  • ISBN13: 978-1-4302-3237-7
  • 336 Pages
  • User Level: Intermediate to Advanced
  • Publication Date: November 22, 2010
  • Available eBook Formats: EPUB, MOBI, PDF

Related Titles

  • Kubernetes Microservices with Docker
  • Learn to Program with Python
  • Learn CakePHP, Second Edition
  • PHP Development Tool Essentials
  • Introducing Linux Distros
  • Building Arduino Projects for  the Internet of Things
  • PHP and MySQL Recipes
  • Spring Persistence with Hibernate, Second Edition
  • Linux Mint for Absolute Beginners
  • 3D Printed Science Projects
Full Description

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

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
Source Code/Downloads

Downloads are available to accompany this book.

Your operating system can likely extract zipped downloads automatically, but you may require software such as WinZip for PC, or StuffIt on a Mac.


If you think that you've found an error in this book, please let us know by emailing to editorial@apress.com . You will find any confirmed erratum below, so you can check if your concern has already been addressed.

On page 19:
Your code sample has a formatting error with the else statement:
def sort_w_check(seq):
n = len(seq)
for i in range(n-1):
if seq[i] > seq[i+1]:

On page 53:

"Subsets, Permutations, and Combinations"

The formula for sum of binomial coefficient is wrong.

it should be k=0 to n SUM (n choose k) = 2 ** n

in the book we have:

k=0 to n SUM (n choose k) = 2 ** k

On page 55 (location 887 in e-book):
There is a typo in the formula that sums combinations. It says 2^k, but it should be 2^n

On page 61:
The text at the end of the solution to recurrence 6 says "That means the sum is equal to the number of nodes, which is \Theta(n)."

But this seems incorrect. The sum should be equal to (2n-1), since it counts the leaf level of the tree (n) as well as the nodes in the tree (n-1), which add up to (2n-1). Of course this is still \Theta(n), but it is not equal to the number of nodes as the book says.

On page 88:

The native algorithm for Topological sorting doesn't work for the following input


Essentially the problem is (i believe), while finding the right place of the nth node in a topologically sorted list of n-1 nodes, it checks after which all nodes in the sorted list the nth node should go.

But if it happens that the nth node is not in the adjacency list of any of the n-1 nodes, but it is in the adjacency of say, (n+m)th node, and this (n+m)th node is in the adjacency list of one of these n-1 nodes, the nth node will go at the start of the list, which is not its right place.

On page 142:
Code for greatest slice is given as

best = A[0]
for size in range(1,n+1):
cur = sum(A[:size])
for i in range(n-size):
cur += A[i+size] -= A[i] #Problem
best = max(best, cur)

There the statement with Problem should be
cur += A[i+size] - A[i]


    1. Unboxing Android USB


      View Book

    2. Beginning AngularJS


      View Book

    3. Beginning Ruby


      View Book

    4. Pro Arduino


      View Book