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.
Table of Contents
- About the Author
- About the Technical Reviewer
- 1. Introduction
2. The Basics
- 2.1. Some Core Ideas in Computing
- 2.2. Asymptotic Notation
- 2.3. Implementing Graphs and Trees
- 2.4. Beware of Black Boxes
- 2.5. Summary
- 2.6. If You're Curious ...
- 2.7. Exercises
- 2.8. References
3. Counting 101
- 3.1. The Skinny on Sums
- 3.2. A Tale of Two Tournaments
- 3.3. Subsets, Permutations, and Combinations
- 3.4. Recursion and Recurrences
- 3.5. So What Was All That About?
- 3.6. Summary
- 3.7. If You're Curious ...
- 3.8. Exercises
- 3.9. References
4. Induction and Recursion ... and Reduction
- 4.1. Oh, That's Easy!
- 4.2. One, Two, Many
- 4.3. Mirror, Mirror
- 4.4. Designing with Induction (and Recursion)
- 4.5. Stronger Assumptions
- 4.6. Invariants and Correctness
- 4.7. Relaxation and Gradual Improvement
- 4.8. Reduction + Contraposition = Hardness Proof
- 4.9. Problem Solving Advice
- 4.10. Summary
- 4.11. If You're Curious ...
- 4.12. Exercises
- 4.13. References
5. Traversal: The Skeleton Key of Algorithmics
- 5.1. A Walk in the Park
- 5.2. Go Deep!
- 5.3. Infinite Mazes and Shortest (Unweighted) Paths
- 5.4. Strongly Connected Components
- 5.5. Summary
- 5.6. If You're Curious ...
- 5.7. Exercises
- 5.8. References
6. Divide, Combine, and Conquer
- 6.1. Tree-Shaped Problems: All About the Balance
- 6.2. The Canonical D&C Algorithm
- 6.3. Searching by Halves
- 6.4. Sorting by Halves
- 6.5. Three More Examples
- 6.6. Tree Balance ... and Balancing*
- 6.7. Summary
- 6.8. If You're Curious ...
- 6.9. Exercises
- 6.10. References
7. Greed Is Good? Prove It!
- 7.1. Staying Safe, Step by Step
- 7.2. The Knapsack Problem
- 7.3. Huffman's Algorithm
- 7.4. Minimum spanning trees
- 7.5. Greed Works. But When?
- 7.6. Summary
- 7.7. If You're Curious ...
- 7.8. Exercises
- 7.9. References
- 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
- 11.1. Reduction Redux
- 11.2. Not in Kansas Anymore?
- 11.3. Meanwhile, Back in Kansas ...
- 11.4. But Where Do You Start? And Where Do You Go from There?
- 11.5. A Ménagerie of Monsters
- 11.6. When the Going Gets Tough, the Smart Get Sloppy
- 11.7. Desperately Seeking Solutions
- 11.8. And the Moral of the Story Is ...
- 11.9. Summary
- 11.10. If You're Curious ...
- 11.11. Exercises
- 11.12. References
- A. Pedal to the Metal: Accelerating Python
- B. List of Problems and Algorithms
- C. Graph Terminology
- D. Hints for Exercises
- Title: Python Algorithms: Mastering Basic Algorithms in the Python Language
- Release date: November 2010
- Publisher(s): Apress
- ISBN: 9781430232377