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.
  • 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.