# 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