Category:Tutorials: Difference between revisions
Jump to navigation
Jump to search
imported>Kmk21 No edit summary |
imported>Kmk21 No edit summary |
||
| Line 1: | Line 1: | ||
=Essential Algorithms= | =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. | 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]] | *[[DP]] | ||
**[[ | **[[Dimension Swapping]] | ||
**[[ | **[[Dimension Elimination]] | ||
**[[ | **[[Row Elimination]] | ||
**[[ | **[[MiniMax]] | ||
** | **using greedy or binary search in the relation | ||
*[[Augmenting Path Algorithms]] | *[[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 | **weight*2^level is equal for all nodes | ||
**can adjust for weighted bars | **can adjust for weighted bars | ||
**can still normalize with unequal bars, just recursively | **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. | **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 | **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 | **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 | **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]] | **[[Convolutions]] | ||
Latest revision as of 16:55, 13 January 2016
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
- Convex Hull
- Segment Tree
- Strongly Connected Components
- Bi Connected Components
- Bipartite Graph
- 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
Pages in category "Tutorials"
The following 30 pages are in this category, out of 30 total.