algorithms README

The project's README from github.com/williamfiset/algorithms. As one markdown file: README.md.

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

Tree algorithms

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

Network flow

Bipartite graph verification (adjacency list) - O(V+E)
:movie_camera: Max flow & Min cut (Ford-Fulkerson with DFS, adjacency list) - O(fE)
Max flow & Min cut (Ford-Fulkerson with DFS, adjacency matrix) - O(fV²)
:movie_camera: Max flow & Min cut (Edmonds-Karp, adjacency list) - O(VE²)
:movie_camera: Max flow & Min cut (Capacity scaling, adjacency list) - O(E²log₂(U))
:movie_camera: 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)
:movie_camera: Bellman-Ford (adjacency list, negative cycles) - O(VE)
:movie_camera: Breadth first search (adjacency list) - O(V+E)
Bridges/cut edges (adjacency list) - O(V+E)
Boruvkas (adjacency list, min spanning tree algorithm) - O(Elog(V))
Find connected components (adjacency list, union find) - O(V+E)
Find connected components (adjacency list, DFS) - O(V+E)
:movie_camera: Depth first search (adjacency list, recursive) - O(V+E)
:movie_camera: Dijkstra's shortest path (adjacency list, lazy implementation) - O(Elog(V))
:movie_camera: Dijkstra's shortest path (adjacency list, eager implementation + D-ary heap) - O(Elog_E/V(V))
:movie_camera: Eulerian Path (directed edges) - O(E+V)
:movie_camera: Floyd Warshall algorithm (adjacency matrix, negative cycle check) - O(V³)
:movie_camera: Kahn's algorithm (topological sort, adjacency list) - O(E+V)
Kruskal's min spanning tree algorithm (edge list, union find) - O(Elog(E))
[Kosaraju's strongly connected components algorithm (adjacency list)](src/main/java/com/williamfiset/algorithms/gr

competitive-programming

Searching Database…

18.8K ·GitHub

What is this?

A large open-source collection of classic algorithms and data structures implemented in Java, written to demonstrate correct implementations in the simplest and most elegant ways.

Is this a library I add to my project, or more of a learning resource?

It's a reference collection rather than a drop-in library: the README shows how to compile and run each implementation on its own, so you read the code and copy what you need.

How do I compile and run an implementation? Do I need Bazel?

You need JDK 8 or newer. Bazel is the recommended build system for running algorithms and tests, but you can skip it and compile any file with plain javac into a classes folder, then run it with java.

Does it tell you the time complexity of each algorithm?

Yes — nearly every entry lists its complexity, like O(Elog(V)) for Dijkstra or O(nlog(n)) for the suffix array construction.

Is the project still being updated?

It dates back to 2017 and is not archived, and GitHub Actions workflows (main.yml, readme-url-checker.yml) are set up in the repo.

Can I copy the code into my own project?

Yes — the project is MIT licensed, so you can use, modify and redistribute the implementations, including in commercial work.

What are similar projects?

Java, cosmos, algo, DSA-Bootcamp-Java, hello-algorithm, JavaScript, awesome-leetcode-resources, algorithms

Which topics is it in?

sorting-algorithms, dynamic-programming, competitive-programming, linear-algebra, mathematics, algorithm, youtube, data-structures, interview-preparation, algorithms, computer-science, reference

Creator: williamfiset
Size: 1.2 GB
Stars: 18.8K
Updated: CommitJun 23
Age: 9y
Commits · 90 Days