Rusty Algorithms and Data Structures for Education & Leetcode Solutions

This repository presents Rust implementations of common algorithms and data structures, most of which are based on William Fiset's Java implementation: https://github.com/williamfiset/Algorithms . I highly recommend his YouTube channel, where he explains many of these algorithms in detail using illustrations, animations and pseudocode.

In addition to implementing W. Fiset's algorithms, I also write solutions to competitive programming problems. Some representative problems are explained in src/problems, and there is also a leetcode folder for my leetcode solutions. Both are far from completion.

Usage

The implementation details are explained in comments and docs and the example usage is implied in unit tests. To run tests:

cargo test

I use LaTeX to write some math expression in docs. To render them correctly in docs, run:

RUSTDOCFLAGS="--html-in-header katex-header.html" cargo doc --no-deps --open

or an alias for this command:

./doc

Recommended Environment

• Editor: Visual Studio Code
  • Extension: rust-analyzer

This simple setup provides most features a decent IDE would provide (importantly, jump to definition and type labelling)

Contents

Graph

Graph Representations

• Adjacency Matrix (Weighted & Unweighted)
• Adjacency List (Weighted & Unweighted)
• Condensed Adjacency Matrix (Weighted)

Fundamental Graph Algorithms

• Depth-first search (iterative and recursive)
• Breadth-first search (iterative)

Tree Algorithms

• Tree representation: with or without pointer to parent
• Fundamentals (DFS, tree height, tree sum, etc.)
• Tree Center
• Tree rooting
• Tree isomorphism
• Lowest common ancestor (LCA)

Minimum Spanning Tree/Forest

• Prim's Algorithm
• Kruskal's Algorithm

Network Flow

• Ford-Fulkerson + DFS
• DFS with capacity scaling
• Edmonds-Karp Algorithm (BFS)
• Dinic's Algorithm (BFS + DFS)

Shortest Path

• BFS (unweighted)
• DAG shortest path with topological sorting
• Dijkstra's algorithm (non-negative weights, SSSP)
• Bellman-Ford algorithm (SSSP)
• Floyd-Warshall algorithm (APSP)

Others

• Bipartite check
• Topological sorting of DAG graphs and DAG shortest path
• Eulerian path/circuit
• Strongly connected components (Tarjan's algorithm)

Data Structures

• Bit manipulation
• Priority queue (binary heap)
• Balanced tree
  • AVL tree
• Disjoin set (union-find)
• Sparse table (range query) (generic)

Machine Learning

Clustering

• Hierarchical clustering

Math

• GCD/LCM
• log2

Problems

Dynamic Programming

• Edit distance
• Knapsack 0/1

Back Tracking

• Sudoku
• N-Queens

Graph

• Travelling salesman problem (brutal force & DP)

Network Flow

• Mice and owls