# Rusty Algorithms and Data Structures for Education & Leetcode Solutions
[![Crates.io](https://img.shields.io/crates/d/algorithms-edu.svg)](https://crates.io/crates/algorithms-edu)
[![Crates.io](https://img.shields.io/crates/v/algorithms-edu.svg)](https://crates.io/crates/algorithms-edu)
[![Crates.io](https://img.shields.io/crates/l/algorithms-edu.svg)](https://crates.io/crates/algorithms-edu)
![Continuous Integration](https://github.com/TianyiShi2001/Algorithms/workflows/CI/badge.svg)
[![Coverage Status](https://coveralls.io/repos/github/TianyiShi2001/Algorithms/badge.svg?branch=main)](https://coveralls.io/github/TianyiShi2001/Algorithms?branch=main)
![lines of code](https://img.shields.io/badge/lines%20of%20code-7221-blue)
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](https://www.youtube.com/user/purpongie), 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. <!-- particularly in Leetcode. Where appropriate, I will note, or `use`, the relevent algorithm/data structure(s) in this crate. -->
## 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](https://github.com/rust-analyzer/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