Method
iterative
Articles
NUM
Algorithm
Euclid's algorithm
The greatest common divisor of two numbers in O(log n) divisions with remainder.
O(log min(a, b))
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
ML
Algorithm
k-means
Splits points into k groups so that points sit close to the centre of their group.
O(n · k · d) per step
2 problems
ML
Algorithm
Perceptron and backpropagation
Draw a digit: a perceptron from 1958 and a network with a hidden layer, both trained right in the page in a second, read it.
perceptron: O(d) per example; network gradient: O(number of weights) per example
1 problem
Problems
Often together
classic 3 interviews 3 images 2 number theory 1 recursion 1 audio 1 security 1 root finding 1 binary search 1 approximation 1 numerical precision 1 science and physics 1