Algorithms and Data Structures

Implementations of algorithms and data structures, code snippets, etc. These algorithms and data structures can be used for everyday programming and competitive programming. The implementation of the algorithms in Rust language has been moved to minaminao/algo-rs.

If you getting the message "Sorry, something went wrong. Reload?" when viewing a Jupyter notebook, try to see nbviewer.

Combinatorics

Algorithm	Implementation	Note
Combinatorics	C++
Factorial	C++
Inclusion–Exclusion Principle	C++
Montmort Numbers	C++
Number of Subsequences	C++
Partition Numbers	C++
Stirling Numbers	C++

Cryptography

These implementations are not secure.

Algorithm	Implementation	Note
ElGamal	C++
RSA	C++

Data Structures

Algorithm	Implementation	Note
Segment Tree
- Range Add Query	C++
- Range Minimum Query	C++
- Range Update Query	C++
Square Root Decomposition
- Range Add Query	C++
- Range Minimum Query	C++
- Range Sum Query	C++
- Range Update Query	C++
- RMQ and RUQ	C++
- RSQ and RAQ	C++
- Square Root Decomposition	C++
Binary Heap	C++
Binary Indexed Tree	C++, Rust
Compression	C++
k-d Tree	C++
Leftist Heap	C++
Sparse Table	C++
Treap	C++
Union–Find	C++, Rust, Python

Dynamic Optimization

Algorithm	Implementation	Note
Digit DP	C++
Dynamic Optimization	C++
Game Theory	C++
Largest Rectangle	C++
Largest Square	C++
Longest Increasing Subsequence	C++
Matrix Chain Multiplication	C++
Traveling Salesman Problem	C++

Geometry

Algorithm	Implementation	Note
Bounding Sphere	C++
Geometry	C++
Geometry 3D	C++
Minimum-Weight Triangulation	C++

Graph Theory

Algorithm	Implementation	Note
Matching
- Bipartite Matching	C++
- Hopcroft–Karp Algorithm	C++
- Lexicographically Bipartite Matching	C++
- Stable Matching	C++
Shortest Path
- 0-1 BFS	C++
- All Pairs Shortest Paths	C++
- BFS	C++
- Bellman–Ford Algorithm	C++
- Build DAG	C++
- Dijkstra's Algorithm	C++
- Get Path	C++
Tree
- Lowest Common Ancestors	C++
- Tree	C++
All Pairs Widest Paths	C++
BFS	C++
Bipartite Graph	C++
Chromatic Polynomial	C++
Cycle Detection	C++
Diameter	C++
DFS	C++
Eulerian Path	C++
Graph	C++
Low-link	C++
Minimum Spanning Arborescence	C++
Minimum Spanning Tree	C++
Strongly Connected Components	C++
Topological Sort	C++

Greedy

Algorithm	Implementation	Note
Activity Selection Problem	C++

Linear Algebra

Algorithm	Implementation	Note
Gauss Elimination	C++
Gauss Elimination Modulo A Prime	C++
Gram–Schmidt Process	C++
Matrix	C++

Machine Learning

Algorithm	Implementation	Note
Least Squares	C++

Number Theory

Algorithm	Implementation	Note
Bernoulli Numbers	C++
Binomial Coefficient	C++
Chinese Remainder Theorem	C++, Python
Divisors	C++
Extended Euclidean Algorithm	C++, Python
Euler's Totient Function	C++
GCD, LCM	C++, Go, Rust
Inverse Element	C++, Python
Legendre's Formula	C++
Log Factorial (Stirling's Approximation)	C++
ModInt	C++
Modular Arithmetic	C++
Number Theory	C++
Polynomial	C++
Primality Test	C++
Prime	C++
Prime Factorization	C++
Quadratic Residue	C++
Radix	C++
Sum Of Powers	C++

Numerical Analysis

Algorithm	Implementation	Note
Bisection Method	C++
Cubic Equation	C++
Lagrange Interpolation	C++
Numerical Analysis	C++
Quadratic Equation	C++

Quantum

Algorithm	Implementation	Note
Adder	C++
Bell State	C++
Bernstein–Vazirani Algorithm	C++
Deutsch's Algorithm	C++
Deutsch–Jozsa Algorithm	C++
Entanglement	C++
GHZ State	C++
n-CNOT	C++
Oracle	C++
Plus State, Minus State	C++
Simon's Algorithm	C++

Signal Processing

Algorithm	Implementation	Note
Fast Fourier Transform	C++

Sort

Algorithm	Implementation	Note
Bubble Sort	C++
Counting Sort	C++
Insertion Sort	C++
Inversion Number	C++
Merge Sort	C++
Minimum Cost Sort	C++
Minimum Numbers Of Swaps	C++
Quick Sort	C++
Sort	C++

String

Algorithm	Implementation	Note
Distance	C++, Python
Fill	C++
Manacher's Algorithm	C++
Morris–Pratt Algorithm	C++
Parser	C++
Replace	C++
Rolling Hash	C++
Split, Join	C++
Suffix Array	C++
Z Algorithm	C++

Others

Algorithm	Implementation	Note
Binary Search	C++, Python
Gray Code	C++
Interactive Problem	C++
Normal Distribution	C++
Number To String	C++
Number To Words	C++
Others	C++
Pop Count	C++
Sliding Windows	C++
String To Number	C++
Sum	C++
Ternary Search	C++

minaminao/algorithms