Dynamic Programming
- Coin change problem - O(nW)
- Edit distance - O(nm)
- Knapsack 0/1 - O(nW)
- Knapsack unbounded (0/∞) - O(nW)
- Maximum contiguous subarray - O(n)
- Longest Common Subsequence (LCS) - O(nm)
- Longest Increasing Subsequence (LIS) - O(n2)
- Longest Palindrome Subsequence (LPS) - O(n2)
- Traveling Salesman Problem (dynamic programming, iterative) - O(n22n)
- Traveling Salesman Problem (dynamic programming, recursive) - O(n22n)
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 cut - 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)
- Line segment-line segment intersection - O(1)
- Longitude-Latitude geographic distance - 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 canonical form (tree isomorphism, tree encoding) - O(Elog(E))
- Tree center(s) - O(V+E)
- Tree diameter - O(V+E)
Network flow
- Bipartite graph verification (adjacency list) - O(V+E)
- Max flow & Min cut (Ford-Fulkerson with DFS, adjacency list) - O(fE)
- Max flow & Min cut (Ford-Fulkerson with DFS, adjacency matrix) - O(fV2)
- Max flow & Min cut (Edmonds-Karp, adjacency list) - O(VE2)
- Max flow & Min cut (Dinic's, adjacency list) - O(EV2)
- Maximum Cardinality Bipartite Matching (augmenting path algorithm, adjacency list) - O(VE)
- Min Cost Max Flow (Bellman-Ford, adjacency list) - O(E2V2)
- Min Cost Max Flow (Johnson's algorithm, adjacency list) - O(E2Vlog(V))
Other graph theory
- Articulation points/cut vertices (adjacency list) - O(V+E)
- Bellman-Ford (edge list, negative cycles, fast & optimized) - O(VE)
- Bellman-Ford (adjacency list, negative cycles) - O(VE)
- Bellman-Ford (adjacency matrix, negative cycles) - O(V3)
- Breadth first search (adjacency list) - O(V+E)
- Breadth first search (adjacency list, fast queue) - O(V+E)
- Bridges/cut edges (adjacency list) - O(V+E)
- Find connected components (adjacency list, union find) - O(Elog(E))
- Find connected components (adjacency list, DFS) - O(V+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, lazy implementation) - O(Elog(V))
- Dijkstra's shortest path (adjacency list, eager implementation + D-ary heap) - O(ElogE/V(V))
- Eulerian Path (directed edges) - O(E+V)
- Floyd Warshall algorithm (adjacency matrix, negative cycle check) - O(V3)
- Graph diameter (adjacency list) - O(VE)
- Kruskal's min spanning tree algorithm (edge list, union find) - O(Elog(E))
- Kruskal's min spanning tree algorithm (edge list, union find, lazy sorting) - 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(V2)
- Prim's min spanning tree algorithm (eager version, adjacency list) - O(Elog(V))
- Steiner tree (minimum spanning tree generalization) - O(V3 + V2 * 2T + V * 3T)
- Tarjan's strongly connected components algorithm (adjacency list) - O(V+E)
- Tarjan's strongly connected components algorithm (adjacency matrix) - O(V2)
- Topological sort (acyclic graph, adjacency list) - O(V+E)
- Topological sort (acyclic graph, adjacency matrix) - O(V2)
- Traveling Salesman Problem (brute force) - O(n!)
- Traveling Salesman Problem (dynamic programming, iterative) - O(n22n)
- Traveling Salesman Problem (dynamic programming, recursive) - O(n22n)
Linear algebra
- Freivald's algorithm (matrix multiplication verification) - O(kn2)
- Gaussian elimination (solve system of linear equations) - O(cr2)
- Gaussian elimination (modular version, prime finite field) - O(cr2)
- Linear recurrence solver (finds nth term in a recurrence relation) - O(m3log(n))
- Matrix determinant (Laplace/cofactor expansion) - O((n+2)!)
- Matrix inverse - O(n3)
- Matrix multiplication - O(n3)
- Matrix power - O(n3log(p))
- Square matrix rotation - O(n2)
Mathematics
- [UNTESTED] 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(n1/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(n1/4)
- Relatively prime check (coprimality check) - ~O(log(a + b))
Other
- Bit manipulations - O(1)
- List permutations - O(n!)
- Power set (set of all subsets) - O(2n)
- Set combinations - O(n choose r)
- Set combinations with repetition - O((n+r-1) choose r)
- Sliding Window Minimum/Maximum - O(1)
- Square Root Decomposition - O(1) point updates, O(√n) range queries
- Unique set combinations - O(n choose r)
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(n2)
- Bucket sort - Θ(n + k)
- Counting sort - O(n + k)
- Heapsort - O(nlog(n))
- Insertion sort - O(n2)
- Mergesort - O(nlog(n))
- Quicksort (in-place, Hoare partitioning) - Θ(nlog(n))
- Selection sort - O(n2)
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 - 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
Contributing
This repository is contribution friendly
For developers
This project uses Gradle as a build system (and testing). Make sure you have Java 8+ SDK installed and the gradle command-line tool. Run the build command to make sure you don't get any errors:
Algorithms$ gradle build
Adding a new algorithm
The procedure to add a new algorithm named Foo is the following:
- Identify the category folder your algorithm belongs to. For example a matrix multiplication snippet would belong to the com/williamfiset/algorithms/linearalgebra folder. You may also create a new category folder if appropriate.
- Add the algorithm implementation to com/williamfiset/algorithms/category/ as com/williamfiset/algorithms/category/Foo.java
- Add tests for Foo in javatests/com/williamfiset/algorithms/category/FooTest.java
- Edit the build.gradle file if you added a new category to the project.
- Test your algorithm thoroughly (see testing section below)
- Send pull request for review 😮
Testing
This repository places a large emphasis on good testing practice to ensure that published algorithms are bug free and high quality. Testing is done using a combinations of frameworks including: JUnit, Mockito and the Google Truth framework. Currently very few algorithms have tests because they were (informally) tested against problems on Kattis in a competitive programming setting, but we are slowly migrating to formally testing these algorithms for robustness. To run all the tests execute:
Algorithms$ gradle test
When developing you likely do not want to run all tests but only a subset of them. For example, if you want to run the FloydWarshallSolverTest.java file under javatests/com/williamfiset/algorithms/graphtheory/FloydWarshallSolverTest.java you can execute:
Algorithms$ gradle test --tests "javatests.com.williamfiset.algorithms.graphtheory.FloydWarshallSolverTest"
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.