This closing topic covers the two Stage-7 branches of the DSA course plan with the clearest direct payoff for quant work, deliberately narrowed from CLRS's full frontier chapters (strings, computational geometry, and dedicated randomized/streaming algorithms are scoped out — see the unit's staging notes). Maximum flow is a specialised optimisation structure that doesn't fit neatly into Topic 6's three named paradigms, solved by the Ford-Fulkerson method and directly applicable to bipartite matching. Complexity theory — , , and -completeness — closes the entire unit by formalising the honest answer to "what if none of this unit's algorithmic toolkit works on my problem?": for a large, well-characterised class of problems, no polynomial-time exact algorithm is known (or, if , exists), and the discipline of recognising this — rather than fruitlessly searching for a fast exact algorithm — is itself a genuinely valuable skill.
By the end of this topic you should be able to:
- state a flow network and the max-flow problem, and derive the Ford-Fulkerson method via augmenting paths.
- prove the max-flow min-cut theorem and use it to certify a flow is maximum.
- reduce bipartite matching to a max-flow instance.
- state the classes and , define polynomial-time reducibility, and explain what an -completeness proof establishes.
- recognise, given a new problem, whether it more closely resembles a solvable instance of this unit's toolkit or a candidate for -hardness, and respond appropriately (exact algorithm vs. approximation/heuristic).
In this lesson
- Contents
- The big picture
The full lesson is for members.
Read the full lessonNew to SelfMadeQuant.com? See membership options or explore the curriculum.