# algorithms-edu 0.2.7

Algorithms for pedagogical demonstration
Documentation

# 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

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)

### Fundamental Graph Algorithms

• Depth-first search (iterative and recursive)

### 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

• GCD/LCM
• log2

# Problems

## Dynamic Programming

• Edit distance
• Knapsack 0/1

• Sudoku
• N-Queens

## Graph

• Travelling salesman problem (brutal force & DP)

## Network Flow

• Mice and owls