Algorithms #

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.
  • Dijkstra (non-negative edges)
  • A*
• 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.
• “Matters Computational”, a very interesting collecton of information about methods of computation which “does not usually appear in textbooks on algorithms”.