Essential Algorithms

These algorithms are ones that you are expected to know in the advanced class. Most problems will draw from the algorithms in this list.

• dijkstra
• bfs
• dfs
• floyd warshall
• mst
• greedy
• DP
  • dimension swapping
  • dimension elimination
  • row elimination
  • minimax
  • using greedy or binary search in the relation
• Augmenting Path Algorithms
  • maxflow
    • min-cut
    • innodes/outnodes
  • bipartite matching
• convex hull
• segment tree
• scc
• bcc
• bipartite graph
  • vertex cover
  • max flow
• binary search
• knp
• bezout's identity
• the "mobile" identity
  • weight*2^level is equal for all nodes
  • can adjust for weighted bars
  • can still normalize with unequal bars, just recursively
• catalan #s
• linear programming
• hungarian algorithm
• topological sort
• "fixing a variable"
  • if you don't know how to find which situation is optimal, iterate through all of them and pick the best one. works when solving the rest of the problem given the fixed variable is easy.
• divide and conquer
• fenwick trees
• "interesting points"
  • don't look at all the points, only look at ones where you know something will change
• scan lines
• dimension explosion
  • you add some other dimension to your state, such as how many of a given resource, or whether you've reached some checkpoint. works with DP, dijkstra, maxflow...all sorts of things
• "select an element"
  • have to find the n'th element of a set, but can't compute all...so figure out which smaller subset it fits in, do this until you find the element
• FFT
  • Convolutions