algorithms

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

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

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(n2)
• Longest Palindrome Subsequence (LPS) - O(n2)
• :movie_camera: Traveling Salesman Problem (dynamic programming, iterative) - O(n22n)
• Traveling Salesman Problem (dynamic programming, recursive) - O(n22n)
• Minimum Weight Perfect Matching (iterative, complete graph) - O(n22n)

Dynamic Programming Problem Examples

Adhoc

• :movie_camera: Magic Cows
• :movie_camera: Narrow Art Gallery

Tiling problems

• :movie_camera: Tiling Dominoes
• :movie_camera: Tiling Dominoes and Trominoes
• :movie_camera: Mountain Scenes

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](src/main/java/com/williamfiset/algorithms/geometry/Lin