book

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

by Magnus Lie Hetland

September 2015

Intermediate to advanced

320 pages

12h 30m

English

Apress

Read now

Unlock full access

What’s All This, Then?What the book is about:What the book covers only briefly or partially:What the book isn’t about:Why Are You Here?Some PrerequisitesWhat’s in This BookSummaryIf You’re Curious …ExercisesReferences
Some Core Ideas in ComputingAsymptotic NotationIt’s Greek to Me!Rules of the RoadTaking the Asymptotics for a SpinThree Important CasesEmpirical Evaluation of AlgorithmsImplementing Graphs and TreesAdjacency Lists and the LikeAdjacency MatricesImplementing TreesA Multitude of RepresentationsBeware of Black BoxesHidden SquaresThe Trouble with FloatsSummaryIf You’re Curious …ExercisesReferences
The Skinny on SumsMore GreekWorking with SumsA Tale of Two TournamentsShaking HandsThe Hare and the TortoiseSubsets, Permutations, and CombinationsRecursion and RecurrencesDoing It by HandA Few Important ExamplesGuessing and CheckingThe Master Theorem: A Cookie-Cutter SolutionSo What Was All That About?SummaryIf You’re Curious …ExercisesReferences
Oh, That’s Easy!One, Two, ManyMirror, MirrorDesigning with Induction (and Recursion)Finding a Maximum PermutationThe Celebrity ProblemTopological SortingStronger AssumptionsInvariants and CorrectnessRelaxation and Gradual ImprovementReduction + Contraposition = Hardness ProofProblem Solving AdviceSummaryIf You’re Curious …ExercisesReferences
A Walk in the ParkNo Cycles AllowedHow to Stop Walking in CirclesGo Deep!Depth-First Timestamps and Topological Sorting (Again)Infinite Mazes and Shortest (Unweighted) PathsStrongly Connected ComponentsSummaryIf You’re Curious …ExercisesReferences
Tree-Shaped Problems: All About the BalanceThe Canonical D&C AlgorithmSearching by HalvesTraversing Search Trees … with PruningSelectionSorting by HalvesHow Fast Can We Sort?Three More ExamplesClosest PairConvex HullGreatest SliceTree Balance … and Balancing*SummaryIf You’re Curious …ExercisesReferences
Staying Safe, Step by StepThe Knapsack ProblemFractional KnapsackInteger KnapsackHuffman’s AlgorithmThe AlgorithmThe First Greedy ChoiceGoing the Rest of the WayOptimal MergingMinimum Spanning TreesThe Shortest EdgeWhat About the Rest?Kruskal’s AlgorithmPrim’s AlgorithmGreed Works. But When?Keeping Up with the BestNo Worse Than PerfectStaying SafeSummaryIf You’re Curious …ExercisesReferences
Don’t Repeat YourselfShortest Paths in Directed Acyclic GraphsLongest Increasing SubsequenceSequence ComparisonThe Knapsack Strikes BackBinary Sequence PartitioningSummaryIf You’re Curious …ExercisesReferences
Propagating KnowledgeRelaxing like CrazyFinding the Hidden DAGAll Against AllFar-Fetched SubproblemsMeeting in the MiddleKnowing Where You’re GoingSummaryIf You’re Curious …ExercisesReferences
Bipartite MatchingDisjoint PathsMaximum FlowMinimum CutCheapest Flow and the Assignment Problem*Some ApplicationsSummaryIf You’re Curious …ExercisesReferences
Reduction ReduxNot in Kansas Anymore?Meanwhile, Back in Kansas …But Where Do You Start? And Where Do You Go from There?A Ménagerie of MonstersReturn of the KnapsackCliques and ColoringsPaths and CircuitsWhen the Going Gets Tough, the Smart Get SloppyDesperately Seeking SolutionsAnd the Moral of the Story Is …SummaryIf You’re Curious …ExercisesReferences
ProblemsAlgorithms and Data Structures
Chapter 1Chapter 2Chapter 3Chapter 4Chapter 5Chapter 6Chapter 7Chapter 8Chapter 9Chapter 10Chapter 11

Content preview from Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition

CHAPTER 10

Matchings, Cuts, and Flows

A joyful life is an individual creation that cannot be copied from a recipe.

— Mihaly Csikszentmihalyi, Flow: The Psychology of Optimal Experience

While the previous chapter gave you several algorithms for a single problem, this chapter describes a single algorithm with many variations and applications. The core problem is that of finding maximum flow in a network, and the main solution strategy I’ll be using is the augmenting path method of Ford and Fulkerson. Before tackling the full problem, I’ll guide you through two simpler problems, which are basically special cases (they’re easily reduced to maximum ...