Python Algorithms: Mastering Basic Algorithms in the Python Language

Python Algorithms: Mastering Basic Algorithms in the Python Language

by
Released November 2010
Publisher(s): Apress
ISBN: 9781430232377

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book 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.

Table of contents

  1. Copyright
  2. About the Author
  3. About the Technical Reviewer
  4. Acknowledgments
  5. Preface
  6. 1. Introduction
    1. 1.1. What's All This, Then?
    2. 1.2. Why Are You Here?
    3. 1.3. Some Prerequisites
    4. 1.4. What's in This Book
    5. 1.5. Summary
    6. 1.6. If You're Curious ...
    7. 1.7. Exercises
    8. 1.8. References
  7. 2. The Basics
    1. 2.1. Some Core Ideas in Computing
    2. 2.2. Asymptotic Notation
      1. 2.2.1. It's Greek to Me!
      2. 2.2.2. Rules of the Road
      3. 2.2.3. Taking the Asymptotics for a Spin
      4. 2.2.4. Three Important Cases
      5. 2.2.5. Empirical Evaluation of Algorithms
    3. 2.3. Implementing Graphs and Trees
      1. 2.3.1. Adjacency Lists and the Like
      2. 2.3.2. Adjacency Matrices
      3. 2.3.3. Implementing Trees
      4. 2.3.4. A Multitude of Representations
    4. 2.4. Beware of Black Boxes
      1. 2.4.1. Hidden Squares
      2. 2.4.2. The Trouble with Floats
    5. 2.5. Summary
    6. 2.6. If You're Curious ...
    7. 2.7. Exercises
    8. 2.8. References
  8. 3. Counting 101
    1. 3.1. The Skinny on Sums
      1. 3.1.1. More Greek
      2. 3.1.2. Working with Sums
    2. 3.2. A Tale of Two Tournaments
      1. 3.2.1. Shaking Hands
      2. 3.2.2. The Hare and the Tortoise
    3. 3.3. Subsets, Permutations, and Combinations
    4. 3.4. Recursion and Recurrences
      1. 3.4.1. Doing It by Hand
      2. 3.4.2. A Few Important Examples
      3. 3.4.3. Guessing and Checking
      4. 3.4.4. The Master Theorem: A Cookie-Cutter Solution
    5. 3.5. So What Was All That About?
    6. 3.6. Summary
    7. 3.7. If You're Curious ...
    8. 3.8. Exercises
    9. 3.9. References
  9. 4. Induction and Recursion ... and Reduction
    1. 4.1. Oh, That's Easy!
    2. 4.2. One, Two, Many
    3. 4.3. Mirror, Mirror
    4. 4.4. Designing with Induction (and Recursion)
      1. 4.4.1. Finding a Maximum Permutation
      2. 4.4.2. The Celebrity Problem
      3. 4.4.3. Topological Sorting
    5. 4.5. Stronger Assumptions
    6. 4.6. Invariants and Correctness
    7. 4.7. Relaxation and Gradual Improvement
    8. 4.8. Reduction + Contraposition = Hardness Proof
    9. 4.9. Problem Solving Advice
    10. 4.10. Summary
    11. 4.11. If You're Curious ...
    12. 4.12. Exercises
    13. 4.13. References
  10. 5. Traversal: The Skeleton Key of Algorithmics
    1. 5.1. A Walk in the Park
      1. 5.1.1. No Cycles Allowed
      2. 5.1.2. How to Stop Walking in Circles
    2. 5.2. Go Deep!
      1. 5.2.1. Depth-First Timestamps and Topological Sorting (Again)
    3. 5.3. Infinite Mazes and Shortest (Unweighted) Paths
    4. 5.4. Strongly Connected Components
    5. 5.5. Summary
    6. 5.6. If You're Curious ...
    7. 5.7. Exercises
    8. 5.8. References
  11. 6. Divide, Combine, and Conquer
    1. 6.1. Tree-Shaped Problems: All About the Balance
    2. 6.2. The Canonical D&C Algorithm
    3. 6.3. Searching by Halves
      1. 6.3.1. Traversing Search Trees ... with Pruning
      2. 6.3.2. Selection
    4. 6.4. Sorting by Halves
      1. 6.4.1. How Fast Can We Sort?
    5. 6.5. Three More Examples
      1. 6.5.1. Closest Pair
      2. 6.5.2. Convex Hull
      3. 6.5.3. Greatest Slice
    6. 6.6. Tree Balance ... and Balancing*
    7. 6.7. Summary
    8. 6.8. If You're Curious ...
    9. 6.9. Exercises
    10. 6.10. References
  12. 7. Greed Is Good? Prove It!
    1. 7.1. Staying Safe, Step by Step
    2. 7.2. The Knapsack Problem
      1. 7.2.1. Fractional Knapsack
      2. 7.2.2. Integer Knapsack
    3. 7.3. Huffman's Algorithm
      1. 7.3.1. The Algorithm
      2. 7.3.2. The First Greedy Choice
      3. 7.3.3. Going the Rest of the Way
      4. 7.3.4. Optimal Merging
    4. 7.4. Minimum spanning trees
      1. 7.4.1. The Shortest Edge
      2. 7.4.2. What About the Rest?
      3. 7.4.3. Kruskal's Algorithm
      4. 7.4.4. Prim's Algorithm
    5. 7.5. Greed Works. But When?
      1. 7.5.1. Keeping Up with the Best
      2. 7.5.2. No Worse Than Perfect
      3. 7.5.3. Staying Safe
    6. 7.6. Summary
    7. 7.7. If You're Curious ...
    8. 7.8. Exercises
    9. 7.9. References
  13. 8. Tangled Dependencies and Memoization
    1. 8.1. Don't Repeat Yourself
    2. 8.2. Shortest Paths in Directed Acyclic Graphs
    3. 8.3. Longest Increasing Subsequence
    4. 8.4. Sequence Comparison
    5. 8.5. The Knapsack Strikes Back
    6. 8.6. Binary Sequence Partitioning
    7. 8.7. Summary
    8. 8.8. If You're Curious ...
    9. 8.9. Exercises
    10. 8.10. References
  14. 9. From A to B with Edsger and Friends
    1. 9.1. Propagating Knowledge
    2. 9.2. Relaxing like Crazy
    3. 9.3. Finding the Hidden DAG
    4. 9.4. All Against All
    5. 9.5. Far-Fetched Subproblems
    6. 9.6. Meeting in the Middle
    7. 9.7. Knowing Where You're Going
    8. 9.8. Summary
    9. 9.9. If You're Curious ...
    10. 9.10. Exercises
    11. 9.11. References
  15. 10. Matchings, Cuts, and Flows
    1. 10.1. Bipartite Matching
    2. 10.2. Disjoint Paths
    3. 10.3. Maximum Flow
    4. 10.4. Minimum Cut
    5. 10.5. Cheapest Flow and the Assignment Problem*
    6. 10.6. Some Applications
    7. 10.7. Summary
    8. 10.8. If You're Curious ...
    9. 10.9. Exercises
    10. 10.10. References
  16. 11. Hard Problems and (Limited) Sloppiness
    1. 11.1. Reduction Redux
    2. 11.2. Not in Kansas Anymore?
    3. 11.3. Meanwhile, Back in Kansas ...
    4. 11.4. But Where Do You Start? And Where Do You Go from There?
    5. 11.5. A Ménagerie of Monsters
      1. 11.5.1. Return of the Knapsack
      2. 11.5.2. Cliques and Colorings
      3. 11.5.3. Paths and Circuits
    6. 11.6. When the Going Gets Tough, the Smart Get Sloppy
    7. 11.7. Desperately Seeking Solutions
    8. 11.8. And the Moral of the Story Is ...
    9. 11.9. Summary
    10. 11.10. If You're Curious ...
    11. 11.11. Exercises
    12. 11.12. References
  17. A. Pedal to the Metal: Accelerating Python
  18. B. List of Problems and Algorithms
    1. B.1. Problems
    2. B.2. Algorithms and Data Structures
  19. C. Graph Terminology
  20. D. Hints for Exercises
    1. D.1. Chapter 1
    2. D.2. Chapter 2
    3. D.3. Chapter 3
    4. D.4. Chapter 4
    5. D.5. Chapter 5
    6. D.6. Chapter 6
    7. D.7. Chapter 7
    8. D.8. Chapter 8
    9. D.9. Chapter 9
    10. D.10. Chapter 10
    11. D.11. Chapter 11

Product information

  • Title: Python Algorithms: Mastering Basic Algorithms in the Python Language
  • Author(s):
  • Release date: November 2010
  • Publisher(s): Apress
  • ISBN: 9781430232377