competitive-scala

My personal repertoire of datastructures and utilities written in pure Scala.

All implementations are pure, with the exception of randomized algorithms which rely on an impure random number generator oracle.
All implementations are asymptotically optimal up to a log^k(n) factor. Most of the time the chosen algorithm is indeed optimal, however the operations on the underlying immutable datastructures may require additional time (compared to their impure counterpart), thus the log factor.
All implementations are self-contained: no external libraries are used and files are isolated from each other.

Repertoire

Maximum bipartite matching (unweighted)
Minimum spanning tree (undirected)
Shortest path
- Single source, positive weights, optional early stopping (Dijkstra)
- Single source, negative weights and negative loop detection (Bellman-Ford)
Topological sort
Union-find data structure

Combinatorics
- Count combinations and permutations
Fast Fourier transform (FFT)
- Transformation and its inverse
- Convolution
Matrix arithmetic
- Dimensions, identity and rotations
- Multiplication and element-wise operations
- Gaussian elimination and inverse
Modular arithmetic
- GCD and LCM
- Modular inverse, Bézout identity and Chinese remainder
- Fast exponentiation, sum of powers
- Randomized Miller-Rabin primality test
- Discrete logarithm
Rational arithmetic

Arithmetic expression parser (shunting-yard)
JSON parser (recursive)
Run-length encoding/decoding
String searching
- Longest prefix also a suffix
- Knuth-Morris-Pratt (KMP) search
- Palindrome search
Suffixes
- Suffix array
- Burrows-Wheeler transform and its inverse
- Rotation array
- Longest common prefix (LCP) array