williamfiset / algorithms

A collection of algorithms and data structures

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.

Contributing

This repository is contribution friendly 😃. If you'd like to add or improve an algorithm, your contribution is welcome! Please be sure to check out the Wiki for instructions.

Other programming languages?

This repository provides algorithm implementations in Java, however, there are other forks that provide implementations in other languages, most notably:

• C++/Python: https://github.com/akzare/Algorithms
• Rust: https://github.com/TianyiShi2001/Algorithms

Running an algorithm implementation

To compile and run any of the algorithms here, you need at least JDK version 8. Gradle can make things more convenient for you, but it is not required.

Running with Gradle (recommended)

This project supports the Gradle Wrapper. The Gradle wrapper automatically downloads Gradle the first time it runs, so expect a delay when running the first command below.

If you are on Windows, use gradlew.bat instead of ./gradlew below.

Run a single algorithm like this:

./gradlew run -Palgorithm=<algorithm-subpackage>.<algorithm-class>

Alternatively, you can run a single algorithm specifying the full class name

./gradlew run -Pmain=<algorithm-fully-qualified-class-name>

For instance:

./gradlew run -Palgorithm=search.BinarySearch

or

./gradlew run -Pmain=com.williamfiset.algorithms.search.BinarySearch

Compiling and running with only a 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

• 🎥 Balanced Trees
  • AVL Tree (recursive)
  • Red Black Tree (recursive)
• 🎥 Binary Search Tree
• Splay Tree
• 🎥 Dynamic Array
  • Dynamic array (integer only, fast)
• 🎥 Fenwick Tree
  • Fenwick Tree (range query, point updates)
  • Fenwick Tree (range update, point query)
• Fibonacci Heap
• 🎥 Hashtable
  • Hashtable (double hashing)
  • Hashtable (linear probing)
  • Hashtable (quadratic probing)
  • Hashtable (separate chaining)
• 🎥 Linked List
• 🎥 Priority Queue
  • Min Binary Heap
  • Min Indexed Binary Heap (sorted key-value pairs, similar to hash-table)
  • Min D-Heap
  • 🎥 Min Indexed D-Heap (sorted key-value pairs, similar to hash-table)
• 🎥 Queue
  • Queue (integer only, fixed size, fast)
  • Queue (linked list, generic)
• Segment Tree
  • Segment tree (array based, compact)
  • Segment tree (pointer implementation)
• 🎥 Sparse Table
• 🎥 Stack
  • Stack (integer only, fixed size, fast)
  • Stack (linked list, generic)
  • Stack (array, generic)
• 🎥 Suffix Array
  • Suffix Array (O(n²logn) construction)
  • Suffix Array (O(nlog²(n)) construction)
  • Suffix Array (O(nlog(n)) construction)
• Trie
• 🎥 Union Find

Dynamic Programming

Dynamic Programming Classics

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

Dynamic Programming Problem Examples

Adhoc

• 🎥 Magic Cows
• 🎥 Narrow Art Gallery

Tiling problems

• 🎥 Tiling Dominoes
• 🎥 Tiling Dominoes and Trominoes
• 🎥 Mountain Scenes

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

• 🎥 Rooting an undirected tree - O(V+E)
• 🎥 Identifying isomorphic trees - O(?)
• 🎥 Tree center(s) - O(V+E)
• Tree diameter - O(V+E)
• 🎥 Lowest Common Ancestor (LCA, Euler tour) - O(1) queries, O(nlogn) preprocessing

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

Main graph theory algorithms

• 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)
• 🎥 Kahn's algorithm (topological sort, adjacency list) - O(E+V)
• 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))
• Kosaraju's strongly connected components algorithm (adjacency list) - O(V+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)
• 🎥 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)
• Lazy Range Adder - O(1) range updates, O(n) to finalize all updates

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))
• Quicksort3 (Dutch National Flag algorithm) - Θ(nlog(n))
• Selection sort - O(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)
• 🎥 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 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.

Donate

Consider donating to support my creation of educational content:

algorithms's Issues

Add triangle centroid finding algorithm

Add algorithm for Voronoi diagram

Add Brent's cycle finding algorithm

Add algorithm to find Eulerian circuit on directed/undirected graph

Add algorithm to solve the Steiner tree problem.

Add traveling salesman with DP

The traveling salesman problem can be solved in O(n!) with a brute force but can be reduced to (n²2ⁿ) with DP.

Missing Algorithms

Still need to code up and document usage of how to use the following algorithms. Help is of course always appreciated :)

Graph Theory

Tree related

• Centroid decomposition
• Heavy-Light decomposition
  • Distance between two nodes
  • Lowest common ancestor
• Tree Center(s)
• Tree Diameter
• Tree Isomorphism/canonical form, O(V+E)
• Rooting tree

Strings

• Aho-Corasick
• Boyer-Moore
• Burrows Wheeler
• Longest repeated substring(s)
• Longest common substring(s)
• Suffix array LCP Kasai algorithm
• Suffix array string match O(mlogn)
• Suffix array string match O(m + logn)
• Z-Algorithm

Add plane-plane intersection algorithm

Add Dinics with dynamic trees

Once #30 is complete see if the performance can be improved by using a dynamic tree to obtain O(EVlogV) time complexity.

Setup continuous integration with Travis-CI

Edit .travis.yml file to setup CI on travis-ci.org for more than just broken links

Add bipartite minimum vertex covering

Use Kőnig's theorem.

Add line-sphere intersection

Add algorithm to do the intersection of a line in general form (ax + by + cz + d = 0) with a sphere of radius r centered at some 3D coordinate (x, y, z).

This Kattis problem should be able to verify the functionality of the algorithm: https://open.kattis.com/problems/pop

Add rotating calipers algorithm

Add Aho-Corasick

Add algorithm to find articulation points.

Add introselect algorithm

Add matrix Singular Value Decomposition (SVD)

Add tidal flow algorithm

Add incircle/incenter (circle inside triangle) algorithm

See here for a nice demo. In the actual implementation consider using the barometric coordinate system.

Add algorithm to find Eulerian path on directed/undirected graph

Add quickselect algorithm

Add quickselect algorithm. Quickselect is a selection algorithm to find the kth smallest element in an unordered list.

Add markov chain algorithm

Add Boyer-Moore

Add K-nearest neighbours classifier using K-D tree

Add the BEST algorithm to count all eulerian paths

Add min cost max flow algorithm

Add 2-SAT algorithm

Implement 2SAT algorithm

Here are some good problems to test the algorithm against:
https://open.kattis.com/problems/blackvienna
https://open.kattis.com/problems/pieceittogether
https://open.kattis.com/problems/palindromicdna

Add longest increasing subsequence O(nlogn) implementation.

There's a faster way than the DP approach to solve the LIS problem. It can be solved in O(nlogn) time with a binary search, let's add it to the repo.

Add radix sort

Still need to implement radix sort

Add algorithm to find Eigen vectors/values

Add algorithm to find Eigen vectors/values along with a complete set of unit tests.

Add simple Artificial Neural Network (ANN)

Add circumcircle/circumcenter (circle center with three points)

See here for a nice demo. In the actual implementation consider using the barometric coordinate system.

GaussianElimination explanation

In the GaussianElimination.java file it is written that you should check for consistency and/or multiple solutions before trying to solve, however I don't think that the methods correctly do this for an arbitrary matrix. I think that the solve method should be run first in order to put the matrix into reduced row echelon form and from there the isInconsistent and hasMultipleSolutions can be used correctly. Does this look/sound right?

Add algorithm to perform a bidirectional search

Perform a search where you start at nodes A and B and try to meet in the middle. The algorithm should be able to output the edges/nodes to get from point A to point B.

Add Dinics algorithm

Add algorithm to find bridges in a graph

Add Ant Colony Optimization (ACO) for TSP

Add A* algorithm

Add finding all complete subgraphs (cliques) in graph

Finding all cliques would be great, but the maximal clique is also ok.

Add smallest encompassing circle of multiple points algorithm

Add Max Weight Independent Set (MWIS) for bipartite graphs

Time complexity

Add time complexity to all algorithms in README for ease of lookup.

Add matrix chain multiplication

Matrix chain multiplication can be solved efficiently with DP

Add line segment to line segment intersection

Add line segment intersection and test against:
https://open.kattis.com/problems/segmentintersection

Add excircle/excenter algorithm

See here for a nice demo. In the actual implementation consider using the barometric coordinate system.

Add maximum independent set algorithm

Add algorithm to find hamiltonian path

Add algorithm to color graph with N colors.

Add Floyd's cycle finding algorithm

Add computing N choose R mod prime