Artificial Intelligence (AI)

• Genetic algorithm Knapsack 0/1
• Genetic algorithm text searching

Constructive algorithms

• Combinations - O(n choose r)
• Combinations with Repetition - O((n+r-1) choose r)
• Permutations - O(n!)
• Power set (set of all subsets) - O(2ⁿ)

Dynamic Programming

• Coin change - O(nW)
• Edit distance - O(nm)
• Knapsack 0/1 - O(nW)
• Knapsack unbounded (0/∞) - O(nW)
• Maximum subarray - O(n)
• Longest Common Subsequence (LCS) - O(nm)
• Longest Increasing Subsequence (LIS) - O(n²)
• Longest Palindrome Subsequence (LPS) - O(n²)

Geometry

• Angle between 2D vectors - O(1)
• Angle between 3D vectors - O(1)
• Circle-circle intersection point(s) - O(1)
• Circle-line intersection point(s) - O(1)
• Circle-line segment intersection point(s) - O(1)
• Circle-point tangent line(s) - O(1)
• Closest pair of points (line sweeping algorithm) - O(nlog(n))
• Collinear points test (are three 2D points on the same line) - O(1)
• Convex hull (Graham Scan algorithm) - O(nlog(n))
• Convex hull (Monotone chain algorithm) - O(nlog(n))
• Convex polygon area - O(n)
• Convex polygon contains points - O(log(n))
• Coplanar points test (are four 3D points on the same plane) - O(1)
• Line class (handy infinite line class) - O(1)
• Line-circle intersection point(s) - O(1)
• Line segment-circle intersection point(s) - O(1)
• Line segment to general form (ax + by = c) - O(1)
• Longitude-Latitude geographic distance - O(1)
• Point-circle tangent line(s) - O(1)
• Point is inside triangle check - O(1)
• Point rotation about point - O(1)
• Triangle area algorithms - O(1)
• [UNTESTED] Circle-circle intersection area - O(1)
• [UNTESTED] Circular segment area - O(1)

Graph theory

Tree algorithms

• Tree diameter - O(V+E)
• [UNTESTED] Tree canonical form - O(V+E)

Network flow

• Bipartite graph verification (adjacency list) - O(V+E)
• Ford-Fulkerson method with DFS (max flow, min cut, adjacency list) - O(fE)
• Ford-Fulkerson method with DFS (max flow, min cut, adjacency matrix) - O(fV²)
• Edmonds-Karp Algorithm (max flow, min cut, adjacency list) - O(VE²)
• Edmonds-Karp Algorithm optimized (max flow, min cut, adjacency list) - O(VE²)
• Maximum Cardinality Bipartite Matching (augmenting path algorithm, adjacency list) - O(VE)

Other graph theory

• Bellman-Ford (edge list, negative cycles) - O(VE)
• Bellman-Ford (adjacency list, negative cycles) - O(VE)
• Breadth first search (adjacency list) - O(V+E)
• Breadth first search (adjacency list, fast queue) - O(V+E)
• Find connected components (adjacency list, union find) - O(Elog(E))
• Depth first search (adjacency list, iterative) - O(V+E)
• Depth first search (adjacency list, iterative, fast stack) - O(V+E)
• Depth first search (adjacency list, recursive) - O(V+E)
• Dijkstra's shortest path (adjacency list) - O(Elog(V))
• Dijkstra's shortest path to all nodes (adjacency list) - O(Elog(V))
• Floyd Warshall algorithm (adjacency matrix, negative cycle check) - O(V³)
• Kruskal's min spanning tree algorithm (edge list, union find) - O(Elog(E))
• Prim's min spanning tree algorithm (lazy version, adjacency list) - O(Elog(E))
• Prim's min spanning tree algorithm (lazy version, adjacency matrix) - O(V²)
• Prim's min spanning tree algorithm (eager version, adjacency list) - O(Elog(V))
• Tarjan's strongly connected components algorithm (adjacency list) - O(V+E)
• Tarjan's strongly connected components algorithm (adjacency matrix) - O(V²)
• Topological sort (acyclic graph, adjacency list) - O(V+E)
• Topological sort (acyclic graph, adjacency matrix) - O(V²)
• [UNTESTED] Graph diameter - O(VE)

Linear algebra

• Freivald's algorithm (matrix multiplication verification) - O(kn²)
• Gaussian elimination (solve system of linear equations) - O(cr²)
• Gaussian elimination (modular version, prime finite field) - O(cr²)
• Linear recurrence solver (finds nth term in a recurrence relation) - O(m³log(n))
• Matrix determinant (Laplace/cofactor expansion) - O((n+2)!)
• Matrix inverse - O(n³)
• Matrix multiplication - O(n³)
• Matrix power - O(n³log(p))
• Square matrix rotation - O(n²)

Mathematics

• Chinese remainder theorem
• Prime number sieve (sieve of Eratosthenes) - O(nlog(log(n)))
• Prime number sieve (sieve of Eratosthenes, compressed) - O(nlog(log(n)))
• Totient function (phi function, relatively prime number count) - O(n^1/4)
• Totient function using sieve (phi function, relatively prime number count) - O(nlog(log(n)))
• Extended euclidean algorithm - ~O(log(a + b))
• Greatest Common Divisor (GCD) - ~O(log(a + b))
• Fast Fourier transform (quick polynomial multiplication) - O(nlog(n))
• Fast Fourier transform (quick polynomial multiplication, complex numbers) - O(nlog(n))
• Primality check - O(√n)
• Primality check (Rabin-Miller) - O(k)
• Least Common Multiple (LCM) - ~O(log(a + b))
• Modular inverse - ~O(log(a + b))
• Prime factorization (pollard rho) - O(n^1/4)
• Relatively prime check (coprimality check) - ~O(log(a + b))

Search algorithms

• Binary search (real numbers) - O(log(n))
• Interpolation search (discrete discrete) - O(n) or O(log(log(n))) with uniform input
• Ternary search (real numbers) - O(log(n))
• Ternary search (discrete numbers) - O(log(n))

Sorting algorithms

• Bubble sort - O(n²)
• Bucket sort - Θ(n + k)
• Counting sort - O(n + k)
• Heapsort - O(nlog(n))
• Insertion sort - O(n²)
• Mergesort - O(nlog(n))
• Quicksort (in-place, Hoare partitioning) - Θ(nlog(n))
• Selection sort - O(n²)

String algorithms

• Booth's algorithm (finds lexicographically smallest string rotation) - O(n)
• Knuth-Morris-Pratt algorithm (finds pattern matches in text) - O(n+m)
• Longest Common Prefix (LCP) array (kasai algorithm) - O(nlog(n)) bounded by SA construction, otherwise O(n)
• Longest Common Substring (LCS) - O(nlog(n)) bounded by SA construction, otherwise O(n)
• Longest Repeated Substring (LRS) - O(nlog(n))
• Manacher's algorithm (finds all palindromes in text) - O(n)
• Rabin-Karp algorithm (finds pattern matches in text) - O(n+m)
• Substring verification with suffix array - O(nlog(n)) SA construction and O(mlog(n)) per query

License

This repository is released under the MIT license. In short, this means you are free to use this software in any personal, open-source or commercial projects. Attribution is optional but appreciated.