Method
numerical precision
Articles
GRA
Algorithm
The Bellman–Ford algorithm
Shortest paths with negative edges and finding a negative cycle: V rounds over all edges.
O(V · E)
2 problems
NUM
Algorithm
Big integers
Numbers longer than a machine word: digits in base 10⁹ or 2³⁰, carries, column methods and expensive printing.
addition O(n), column multiplication and division O(n²), printing in decimal O(n²) or O(M(n) log n)
2 problems
NUM
Algorithm
Fast Fourier transform
The discrete Fourier transform in O(N log N): spectra, convolutions, multiplying polynomials and big numbers.
O(N log N)
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
GEO
Technique
Vectors and orientation
The sign of the cross product is a left or right turn; almost all of computational geometry stands on it.
O(1) per turn
2 problems
NUM~
Algorithm
Bisection and Newton's method
A root of an equation: halving an interval is reliable, Newton's tangents are fast.
bisection: log₂((b − a)/ε) steps; Newton: about log₂ of the number of digits
2 problems
Problems
Often together
classic 6 interviews 3 contests 3 graph 2 finance 2 divide and conquer 2 in production 2 science and physics 2 shortest path 1 weighted graph 1 dynamic programming 1 networks 1