Algorithms in Rust

Algorithms in Rust

A collection of some algorithms and data-structures.

• See Change log

Item	Status
Build
Test
Crate

Algorithms

• Discretization
• Dichotomy
  • Lower bound
  • Upper bound
  • Equal range
• Inversion pairs
• Next subset
• Matrix
• Number theory
  • Quick pow, quick multiply
  • Prime factor decompose
  • Prime test
    • Trial O(sqrt)
    • Miller-Rabin
  • GCD, LCM
    • Euclid's algorithm
    • Stein's algorithm
    • Extended Euclid's algorithm
  • Inverse element (Modal meaning)
  • Euler phi function
• Linear sieve
• Trichotomy
• Tree diameter

Data-structures

• Disjoint set
• Monotonic queue
• Sparse Table
• Prefix sum
  • 1D
  • 2D
• Fenwick tree
• Segment tree
• Leftist heap
• Trie
• String hash
• Shortest path
  • Single source
  • Multi source
• Topological sorting
• DFS order
• Minimum spanning tree

Development

$ cargo test