migsr22 / algorithms

A collection of algorithms

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(n²)
• Longest Palindrome Subsequence (LPS) - O(n²)
• 🎥Traveling Salesman Problem (dynamic programming, iterative) - O(n²2ⁿ)
• Traveling Salesman Problem (dynamic programming, recursive) - O(n²2ⁿ)
• Minimum Weight Perfect Matching (iterative, complete graph) - O(n²2ⁿ)

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(fV²)
• 🎥Max flow & Min cut (Edmonds-Karp, adjacency list) - O(VE²)
• 🎥Max flow & Min cut (Capacity scaling, adjacency list) - O(E²log₂(U))
• 🎥Max flow & Min cut (Dinic's, adjacency list) - O(EV²) or O(E√V) for bipartite graphs
• Maximum Cardinality Bipartite Matching (augmenting path algorithm, adjacency list) - O(VE)
• Min Cost Max Flow (Bellman-Ford, adjacency list) - O(E²V²)
• Min Cost Max Flow (Johnson's algorithm, adjacency list) - O(E²Vlog(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(V³)
• 🎥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(Elog_E/V(V))
• 🎥Eulerian Path (directed edges) - O(E+V)
• 🎥Floyd Warshall algorithm (adjacency matrix, negative cycle check) - O(V³)
• 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(V²)
• Prim's min spanning tree algorithm (eager version, adjacency list) - O(Elog(V))
• Steiner tree (minimum spanning tree generalization) - O(V³ + V² * 2^T + V * 3^T)
• 🎥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²)
• Traveling Salesman Problem (brute force) - O(n!)
• 🎥Traveling Salesman Problem (dynamic programming, iterative) - O(n²2ⁿ)
• Traveling Salesman Problem (dynamic programming, recursive) - O(n²2ⁿ)

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

• [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(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))

Other

• Bit manipulations - O(1)
• List permutations - O(n!)
• 🎥Power set (set of all subsets) - O(2ⁿ)
• 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(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 - 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 😃. If you're an algorithms enthusiast (like me!) and want to add or improve an algorithm your contribution is welcome! Please be sure to include tests 😘.

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:

1. 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.
2. Add the algorithm implementation to com/williamfiset/algorithms/category/ as com/williamfiset/algorithms/category/Foo.java
3. Add tests for Foo in javatests/com/williamfiset/algorithms/category/FooTest.java
4. Edit the build.gradle file if you added a new category to the project.
5. Test your algorithm thoroughly (see testing section below)
6. 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.