Recursion
Divide and conquer
Finding interesting points in N log N
Algorithm analysis
Master theorem
Amortized time complexity
Greedy algorithm
Scheduling
Max contigous subvector sum
Invariants
Huffman encoding
Graph teory
Dynamic graphs (extra book-keeping)
Breadth first search
Depth first search
* Normal trees / DFS trees
Dijkstra’s algoritm
MST: Prim’s algoritm
Bellman-Ford
Konig’s theorem and vertex cover
Min-cost max flow
Lovasz toggle
Matrix tree theorem
Maximal matching, general graphs
Hopcroft-Karp
Hall’s marriage theorem
Graphical sequences
Floyd-Warshall
Eulercykler
Flow networks
* Augumenting paths
* Edmonds-Karp
Bipartite matching
Min. path cover
Topological sorting
Strongly connected components
2-SAT
Cutvertices, cutedges och biconnected components
Edge coloring
* Trees
Vertex coloring
* Bipartite graphs (=> trees)
* 3^n (special case of set cover)
Diameter and centroid
K’th shortest path
Shortest cycle
Dynamic programming
Knapsack
Coin change
Longest common subsequence
Longest increasing subsequence
Number of paths in a dag
Shortest path in a dag
Dynprog over intervals
Dynprog over subsets
Dynprog over probabilities
Dynprog over trees
3^n set cover
Divide and conquer
Knuth optimization
Convex hull optimizations
RMQ (sparse table a.k.a 2^k-jumps)
Bitonic cycle
Log partitioning (loop over most restricted)
Combinatorics
Computation of binomial coefficients
Pigeon-hole principle
Inclusion/exclusion
Catalan number
Pick’s theorem
Number theory
Integer parts
Divisibility
Euklidean algorithm
Modular arithmetic
* Modular multiplication
* Modular inverses
* Modular exponentiation by squaring
Chinese remainder theorem
Fermat’s small theorem
Euler’s theorem
Phi function
Frobenius number
Quadratic reciprocity
Pollard-Rho
Miller-Rabin
Hensel lifting
Vieta root jumping
Game theory
Combinatorial games
Game trees
Mini-max
Nim
Games on graphs
Games on graphs with loops
Grundy numbers
Bipartite games without repetition
General games without repetition
Alpha-beta pruning
Probability theory
Optimization
Binary search
Ternary search
Unimodality and convex functions
Binary search on derivative
Numerical methods
Numeric integration
Newton’s method
Root-finding with binary/ternary search
Golden section search
Matrices
Gaussian elimination
Exponentiation by squaring
Sorting
Radix sort
Geometry
Coordinates and vectors
* Cross product
* Scalar product
Convex hull
Polygon cut
Closest pair
Coordinate-compression
Quadtrees
KD-trees
All segment-segment intersection
Sweeping
Discretization (convert to events and sweep)
Angle sweeping
Line sweeping
Discrete second derivatives
Strings
Longest common substring
Palindrome subsequences
Knuth-Morris-Pratt
Tries
Rolling polynom hashes
Suffix array
Suffix tree
Aho-Corasick
Manacher’s algorithm
Letter position lists
Combinatorial search
Meet in the middle
Brute-force with pruning
Best-first (A*)
Bidirectional search
Iterative deepening DFS / A*
Data structures
LCA (2^k-jumps in trees in general)
Pull/push-technique on trees
Heavy-light decomposition
Centroid decomposition
Lazy propagation
Self-balancing trees
Convex hull trick (Convex hull trick - PEGWiki)
Monotone queues / monotone stacks / sliding queues
Sliding queue using 2 stacks
Persistent segment tree