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 6. Divide, Combine, and Conquer

Divide and rule, a sound motto;

Unite and lead, a better one.

--Johann Wolfgang von Goethe, Gedichte

This chapter is the first of three dealing with well-known design strategies. The strategy dealt with in this chapter, divide and conquer (or simply D&C), is based on decomposing your problem in a way that improves performance. You divide the problem instance, solve subproblems recursively, combine the results, and thereby conquer the problem—a pattern that is reflected in the chapter title.^[69]

Tree-Shaped Problems: All About the Balance

I have mentioned the idea of a subproblem graph before: we view subproblems as nodes and dependencies (or reductions) as edges. The simplest structure such a subproblem graph ...

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

Publisher Resources

ISBN: 9781430232377Purchase book

Python Algorithms: Mastering Basic Algorithms in the Python Language

by Magnus Lie Hetland

Chapter 6. Divide, Combine, and Conquer

Tree-Shaped Problems: All About the Balance

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.

You might also like