book

Python Algorithms: Mastering Basic Algorithms in the Python Language

by Magnus Lie Hetland

November 2010

Intermediate to advanced

332 pages

11h 57m

English

Apress

Read now

Unlock full access

1.1. What's All This, Then?1.2. Why Are You Here?1.3. Some Prerequisites1.4. What's in This Book1.5. Summary1.6. If You're Curious ...1.7. Exercises1.8. References
2.1. Some Core Ideas in Computing2.2. Asymptotic Notation2.2.1. It's Greek to Me!2.2.2. Rules of the Road2.2.3. Taking the Asymptotics for a Spin2.2.4. Three Important Cases2.2.5. Empirical Evaluation of Algorithms2.3. Implementing Graphs and Trees2.3.1. Adjacency Lists and the Like2.3.2. Adjacency Matrices2.3.3. Implementing Trees2.3.4. A Multitude of Representations2.4. Beware of Black Boxes2.4.1. Hidden Squares2.4.2. The Trouble with Floats2.5. Summary2.6. If You're Curious ...2.7. Exercises2.8. References
3.1. The Skinny on Sums3.1.1. More Greek3.1.2. Working with Sums3.2. A Tale of Two Tournaments3.2.1. Shaking Hands3.2.2. The Hare and the Tortoise3.3. Subsets, Permutations, and Combinations3.4. Recursion and Recurrences3.4.1. Doing It by Hand3.4.2. A Few Important Examples3.4.3. Guessing and Checking3.4.4. The Master Theorem: A Cookie-Cutter Solution3.5. So What Was All That About?3.6. Summary3.7. If You're Curious ...3.8. Exercises3.9. References
4.1. Oh, That's Easy!4.2. One, Two, Many4.3. Mirror, Mirror4.4. Designing with Induction (and Recursion)4.4.1. Finding a Maximum Permutation4.4.2. The Celebrity Problem4.4.3. Topological Sorting4.5. Stronger Assumptions4.6. Invariants and Correctness4.7. Relaxation and Gradual Improvement4.8. Reduction + Contraposition = Hardness Proof4.9. Problem Solving Advice4.10. Summary4.11. If You're Curious ...4.12. Exercises4.13. References
5.1. A Walk in the Park5.1.1. No Cycles Allowed5.1.2. How to Stop Walking in Circles5.2. Go Deep!5.2.1. Depth-First Timestamps and Topological Sorting (Again)5.3. Infinite Mazes and Shortest (Unweighted) Paths5.4. Strongly Connected Components5.5. Summary5.6. If You're Curious ...5.7. Exercises5.8. References

6.1. Tree-Shaped Problems: All About the Balance6.2. The Canonical D&C Algorithm6.3. Searching by Halves6.3.1. Traversing Search Trees ... with Pruning6.3.2. Selection6.4. Sorting by Halves6.4.1. How Fast Can We Sort?6.5. Three More Examples6.5.1. Closest Pair6.5.2. Convex Hull6.5.3. Greatest Slice6.6. Tree Balance ... and Balancing*6.7. Summary6.8. If You're Curious ...6.9. Exercises6.10. References
7.1. Staying Safe, Step by Step7.2. The Knapsack Problem7.2.1. Fractional Knapsack7.2.2. Integer Knapsack7.3. Huffman's Algorithm7.3.1. The Algorithm7.3.2. The First Greedy Choice7.3.3. Going the Rest of the Way7.3.4. Optimal Merging7.4. Minimum spanning trees7.4.1. The Shortest Edge7.4.2. What About the Rest?7.4.3. Kruskal's Algorithm7.4.4. Prim's Algorithm7.5. Greed Works. But When?7.5.1. Keeping Up with the Best7.5.2. No Worse Than Perfect7.5.3. Staying Safe7.6. Summary7.7. If You're Curious ...7.8. Exercises7.9. References
8.1. Don't Repeat Yourself8.2. Shortest Paths in Directed Acyclic Graphs8.3. Longest Increasing Subsequence8.4. Sequence Comparison8.5. The Knapsack Strikes Back8.6. Binary Sequence Partitioning8.7. Summary8.8. If You're Curious ...8.9. Exercises8.10. References
9.1. Propagating Knowledge9.2. Relaxing like Crazy9.3. Finding the Hidden DAG9.4. All Against All9.5. Far-Fetched Subproblems9.6. Meeting in the Middle9.7. Knowing Where You're Going9.8. Summary9.9. If You're Curious ...9.10. Exercises9.11. References
10.1. Bipartite Matching10.2. Disjoint Paths10.3. Maximum Flow10.4. Minimum Cut10.5. Cheapest Flow and the Assignment Problem*10.6. Some Applications10.7. Summary10.8. If You're Curious ...10.9. Exercises10.10. References
11.1. Reduction Redux11.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 Monsters11.5.1. Return of the Knapsack11.5.2. Cliques and Colorings11.5.3. Paths and Circuits11.6. When the Going Gets Tough, the Smart Get Sloppy11.7. Desperately Seeking Solutions11.8. And the Moral of the Story Is ...11.9. Summary11.10. If You're Curious ...11.11. Exercises11.12. References
B.1. ProblemsB.2. Algorithms and Data Structures
D.1. Chapter 1D.2. Chapter 2D.3. Chapter 3D.4. Chapter 4D.5. Chapter 5D.6. Chapter 6D.7. Chapter 7D.8. Chapter 8D.9. Chapter 9D.10. Chapter 10D.11. Chapter 11

Content preview from Python Algorithms: Mastering Basic Algorithms in the Python Language

Chapter 5. Traversal: The Skeleton Key of Algorithmics

	You are in a narrow hallway. This continues for several metres and ends in a doorway. Halfway along the passage you can see an archway where some steps lead downwards. Will you go forwards to the door (turn to 5), or creep down the steps (turn to 344)?
	--Steve Jackson, Citadel of Chaos

Graphs are a powerful mental (and mathematical) model of structure in general; if you can formulate a problem as one dealing with graphs, even if it doesn't look like a graph problem, you are probably one step closer to solving it. It just so happens that there is a highly useful mental model for graph algorithms as well—a skeleton key, if you will.^[50] That skeleton key is traversal: discovering, and later ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Start your free trial

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

Magnus Lie Hetland

Python 3: Project-based Python, Algorithms, Data Structures

Mashrur Hossain

Working with Algorithms in Python

George T. Heineman

Distributed Machine Learning with Python

Guanhua Wang

Publisher Resources

ISBN: 9781430232377Purchase book