List of problems and algorithms used to solve them
- Min-cost flow problem (find the flow in a flow network of minimal cost)
- Out-of-kilter (which solves min-cost flow in \(O(e^2U + eUv\log v)\), no longer the state-of-the-art)
- Shortest path problem (find the shortest path between two points in a graph)
Used all the time in game development for AI pathfinding.
- Secretary problem, for which an asymptotically optimal strategy can be found.
Links and resources
- A nice list of lesser-known algorithms that are useful in system design.
- A primer on the out-of-kilter algorithm written for the US Air Force as part of Project RAND.
- A nice course from Stanford on modern applied algorithms with all course notes and assignments available online.
- The Complexity Zoo, which maps out the connections between all different complexity classes.