Solves
linear algebra
Articles
DP
Technique
Interval DP
The state is an interval [i, j], the transition is where to cut it: search trees, matrix chain order, sawing.
O(n³)
2 problems
NUM
Algorithm
Chinese remainder theorem
A number from its residues modulo several moduli: Garner's algorithm and exact computation over many primes.
O(k²) operations on machine numbers
2 problems
NUM
Algorithm
Gaussian elimination
A linear system by elimination: the pivot, LU, conditioning, sparse matrices and fill-in.
O(n³): about n³/3 multiplications for the forward pass
2 problems
Problems
Often together
matrix 3 classic 3 graph 2 dynamic programming 1 optimization 1 search tree 1 prefix sums 1 bioinformatics 1 contests 1 number theory 1 counting 1 maps and navigation 1