O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition

Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition

by Magnus Lie Hetland
Publisher: Apress
Release Date: September 2015
ISBN: 9781484200551
View table of contents
Start reading

Book Description

Python Algorithms, Second Edition 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 in a highly readable manner. It 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.

Table of Contents

  1. Cover
  2. Title
  3. Copyright
  4. Dedication
  5. Contents at a Glance
  6. Contents
  7. About the Author
  8. About the Technical Reviewer
  9. Acknowledgments
  10. Preface
  11. Chapter 1: Introduction
    1. What’s All This, Then?
      1. What the book is about:
      2. What the book covers only briefly or partially:
      3. What the book isn’t about:
    2. Why Are You Here?
    3. Some Prerequisites
    4. What’s in This Book
    5. Summary
    6. If You’re Curious …
    7. Exercises
    8. References
  12. Chapter 2: The Basics
    1. Some Core Ideas in Computing
    2. Asymptotic Notation
      1. It’s Greek to Me!
      2. Rules of the Road
      3. Taking the Asymptotics for a Spin
      4. Three Important Cases
      5. Empirical Evaluation of Algorithms
    3. Implementing Graphs and Trees
      1. Adjacency Lists and the Like
      2. Adjacency Matrices
      3. Implementing Trees
      4. A Multitude of Representations
    4. Beware of Black Boxes
      1. Hidden Squares
      2. The Trouble with Floats
    5. Summary
    6. If You’re Curious …
    7. Exercises
    8. References
  13. Chapter 3: Counting 101
    1. The Skinny on Sums
      1. More Greek
      2. Working with Sums
    2. A Tale of Two Tournaments
      1. Shaking Hands
      2. The Hare and the Tortoise
    3. Subsets, Permutations, and Combinations
    4. Recursion and Recurrences
      1. Doing It by Hand
      2. A Few Important Examples
      3. Guessing and Checking
      4. The Master Theorem: A Cookie-Cutter Solution
    5. So What Was All That About?
    6. Summary
    7. If You’re Curious …
    8. Exercises
    9. References
  14. Chapter 4: Induction and Recursion … and Reduction
    1. Oh, That’s Easy!
    2. One, Two, Many
    3. Mirror, Mirror
    4. Designing with Induction (and Recursion)
      1. Finding a Maximum Permutation
      2. The Celebrity Problem
      3. Topological Sorting
    5. Stronger Assumptions
    6. Invariants and Correctness
    7. Relaxation and Gradual Improvement
    8. Reduction + Contraposition = Hardness Proof
    9. Problem Solving Advice
    10. Summary
    11. If You’re Curious …
    12. Exercises
    13. References
  15. Chapter 5: Traversal: The Skeleton Key of Algorithmics
    1. A Walk in the Park
      1. No Cycles Allowed
      2. How to Stop Walking in Circles
    2. Go Deep!
      1. Depth-First Timestamps and Topological Sorting (Again)
    3. Infinite Mazes and Shortest (Unweighted) Paths
    4. Strongly Connected Components
    5. Summary
    6. If You’re Curious …
    7. Exercises
    8. References
  16. Chapter 6: Divide, Combine, and Conquer
    1. Tree-Shaped Problems: All About the Balance
    2. The Canonical D&C Algorithm
    3. Searching by Halves
      1. Traversing Search Trees … with Pruning
      2. Selection
    4. Sorting by Halves
      1. How Fast Can We Sort?
    5. Three More Examples
      1. Closest Pair
      2. Convex Hull
      3. Greatest Slice
    6. Tree Balance … and Balancing*
    7. Summary
    8. If You’re Curious …
    9. Exercises
    10. References
  17. Chapter 7: Greed Is Good? Prove It!
    1. Staying Safe, Step by Step
    2. The Knapsack Problem
      1. Fractional Knapsack
      2. Integer Knapsack
    3. Huffman’s Algorithm
      1. The Algorithm
      2. The First Greedy Choice
      3. Going the Rest of the Way
      4. Optimal Merging
    4. Minimum Spanning Trees
      1. The Shortest Edge
      2. What About the Rest?
      3. Kruskal’s Algorithm
      4. Prim’s Algorithm
    5. Greed Works. But When?
      1. Keeping Up with the Best
      2. No Worse Than Perfect
      3. Staying Safe
    6. Summary
    7. If You’re Curious …
    8. Exercises
    9. References
  18. Chapter 8: Tangled Dependencies and Memoization
    1. Don’t Repeat Yourself
    2. Shortest Paths in Directed Acyclic Graphs
    3. Longest Increasing Subsequence
    4. Sequence Comparison
    5. The Knapsack Strikes Back
    6. Binary Sequence Partitioning
    7. Summary
    8. If You’re Curious …
    9. Exercises
    10. References
  19. Chapter 9: From A to B with Edsger and Friends
    1. Propagating Knowledge
    2. Relaxing like Crazy
    3. Finding the Hidden DAG
    4. All Against All
    5. Far-Fetched Subproblems
    6. Meeting in the Middle
    7. Knowing Where You’re Going
    8. Summary
    9. If You’re Curious …
    10. Exercises
    11. References
  20. Chapter 10: Matchings, Cuts, and Flows
    1. Bipartite Matching
    2. Disjoint Paths
    3. Maximum Flow
    4. Minimum Cut
    5. Cheapest Flow and the Assignment Problem*
    6. Some Applications
    7. Summary
    8. If You’re Curious …
    9. Exercises
    10. References
  21. Chapter 11: Hard Problems and (Limited) Sloppiness
    1. Reduction Redux
    2. Not in Kansas Anymore?
    3. Meanwhile, Back in Kansas …
    4. But Where Do You Start? And Where Do You Go from There?
    5. A Ménagerie of Monsters
      1. Return of the Knapsack
      2. Cliques and Colorings
      3. Paths and Circuits
    6. When the Going Gets Tough, the Smart Get Sloppy
    7. Desperately Seeking Solutions
    8. And the Moral of the Story Is …
    9. Summary
    10. If You’re Curious …
    11. Exercises
    12. References
  22. Appendix A: Pedal to the Metal: Accelerating Python
  23. Appendix B: List of Problems and Algorithms
    1. Problems
    2. Algorithms and Data Structures
  24. Appendix C: Graph Terminology
  25. Appendix D: Hints for Exercises
    1. Chapter 1
    2. Chapter 2
    3. Chapter 3
    4. Chapter 4
    5. Chapter 5
    6. Chapter 6
    7. Chapter 7
    8. Chapter 8
    9. Chapter 9
    10. Chapter 10
    11. Chapter 11
  26. Index