# Algorithms

See CppCon 2018: Jonathan Boccara: 105 STL Algorithms in Less Than an Hour.

## Secret runes

• stable_
• is_
• is_*_until

See Introsort and sorting algorithms.

## Algorithm patterns

• Brute Force
• Divide and Conquer: Karatsuba’s Integer Multiplication -- it is possible to perform multiplication of large numbers in (many) fewer operations than the usual brute-force technique of "long multiplication." As discovered by Karatsuba (Karatsuba and Ofman 1962).
• Decrease and Conquer
• The Greedy Method
• Dynamic Programming
• Backtracking
• "Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems."
• Hill Climbing
• Particle Swarm Optimisation
• Las Vegas
• Monte Carlo
• Reduction (Transformation)
• Preprocessing
• "Gradient descent is a first-order iterative optimization algorithm for finding a local minimum of a differentiable function."

## Big-O notation

Big-O notations is a technique to describe the complexity of an algorithm as the data set becomes larger.

Be prepared to write code. Remember your merge sort, quick sort, binary search, etc, and be able to write them cold.

Complexity name
O(1) constant
O(log n) logarithmic
O(n) linear
O(n log n)=O(log n!) linearithmic