Algorithms & data structures project

Algorithms and data structures are fundamental to efficient code and good software design. Creating and designing excellent algorithms is required for being an exemplary programmer. This repository's goal is to demonstrate how to correctly implement common data structures and algorithms in the simplest and most elegant ways.

🎬 Many of the algorithms and data structures in this repo have companion video explanations on the William Fiset YouTube channel — so if the code alone doesn't click, grab some popcorn and watch the videos!

Running an algorithm implementation

To compile and run any of the algorithms here, you need at least JDK version 8 and Bazel

Running with Bazel (recommended)

This project uses Bazel as its build system. Install Bazel by following the official installation guide.

Run a single algorithm like this:

bazel run //src/main/java/com/williamfiset/algorithms/<subpackage>:<ClassName>

For instance:

bazel run //src/main/java/com/williamfiset/algorithms/search:BinarySearch

Run all tests:

bazel test //src/test/...

Run tests for a specific package:

bazel test //src/test/java/com/williamfiset/algorithms/sorting:all

Compiling and running with only a JDK

If you don't want to use Bazel, you can compile and run with just the JDK:

Create a classes folder

cd Algorithms
mkdir classes

Compile the algorithm

javac -sourcepath src/main/java -d classes src/main/java/<relative-path-to-java-source-file>

Run the algorithm

java -cp classes <class-fully-qualified-name>

Example

$ javac -d classes -sourcepath src/main/java src/main/java/com/williamfiset/algorithms/search/BinarySearch.java
$ java -cp classes com.williamfiset.algorithms.search.BinarySearch

Data Structures

Dynamic Programming

Dynamic Programming Classics

Coin change problem - O(nW)
Edit distance (iterative) - O(nm)
Edit distance (recursive) - O(nm)
:movie_camera: 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²)
:movie_camera: 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ⁿ)

Dynamic Programming Problem Examples

Adhoc

Tiling problems

Geometry

Angle between 2D 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))
Triangle area algorithms - O(1)
Line segment-circle intersection point(s) - O(1)
Line segment-line segment intersection - O(1)

More geometry algorithms

Angle between 3D vectors - O(1)
Convex polygon cut - O(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 to general form (ax + by = c) - O(1)
Longitude-Latitude geographic distance - O(1)
Point is inside triangle check - O(1)
Point rotation about point - 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

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)
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)
Least Common Multiple (LCM) - ~O(log(a + b))
Modular inverse - ~O(log(a + b))
Modular exponentiation - O(log(n))
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!)
:movie_camera: Power set (set of all subsets) - O(n · 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 numbers) - 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²)
:movie_camera: Mergesort - O(nlog(n))
Quicksort (in-place, Hoare partitioning) - Θ(nlog(n))
Quicksort3 (Dutch National Flag algorithm) - Θ(nlog(n))
Selection sort - O(n²)
Shell sort - O(n²) worst, ~O(n^1.5) average
Tim sort - O(nlog(n))
Radix sort - O(n*w)

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)
:movie_camera: Longest Common Substring (LCS) - O(nlog(n)) bounded by SA construction, otherwise O(n)
:movie_camera: Longest Repeated Substring (LRS) - O(nlog(n))
Manacher's algorithm (finds all palindromes in text) - O(n)
Rabin-Karp algorithm (finds pattern match positions 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.

Sponsor

Consider sponsoring to support my creation of educational content:

williamfiset/algorithms

Measured star growth

README.md