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ⁿ)

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-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

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:

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.

SumitLubal/Algorithms