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
• Minimum Spanning Tree
• Greedy
• DP
  • Dimension Swapping
  • Dimension Elimination
  • Row Elimination
  • MiniMax
  • using greedy or binary search in the relation
• Augmenting Path Algorithms
  • Max Flow
    • Min Cut
    • In-Out Nodes
  • Bipartite Matching
• Convex Hull
• Segment Tree
• Strongly Connected Components
• Bi Connected Components
• Bipartite Graph
  • Vertex Cover
  • Max Flow
• Binary Search
• KNP
• Bezout's Identity
• Mobile Identity
  • weight*2^level is equal for all nodes
  • can adjust for weighted bars
  • can still normalize with unequal bars, just recursively
• Catalan Numbers
• 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 Line
• 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
• Fast Fourier Transform
  • Convolutions