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

Searching Database…

18.8K ·GitHub

这是什么?

一个大型开源项目,收录了用 Java 实现的经典算法和数据结构,目的是用最简单、最优雅的写法展示正确的实现。

这是可以直接加到我项目里的库,还是更像一份学习资料?

它更像一份参考合集,而不是拿来即用的库:README 演示了如何单独编译和运行每个实现,你可以先读代码,再把需要的内容复制过去。

怎么编译和运行某个实现?一定要用 Bazel 吗?

需要 JDK 8 或更高版本。Bazel 是推荐的构建工具,用来运行算法和测试,但你也可以不用它,直接用 javac 把任意文件编译到 classes 文件夹,然后用 java 运行。

它标出每个算法的时间复杂度吗?

有——几乎每个条目都列出了复杂度,比如 Dijkstra 是 O(Elog(V)),后缀数组的构建是 O(nlog(n))。

这个项目还在更新吗?

项目创建于 2017 年,目前没有被归档,仓库里也配置了 GitHub Actions 工作流(main.yml、readme-url-checker.yml)。

我可以把代码复制到自己的项目里吗?

可以——项目采用 MIT 许可证,你可以使用、修改和分发这些实现,包括用于商业用途。

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