Algos

🚧 Work in Progress 🚧

This crate is undergoing significant development. It aims to be a comprehensive collection of algorithms implemented in Rust, serving both as a learning resource and a practical library.

Recent Changes

Jan 16, 2025 - ADVISORY: This crate has changed hands and will be maintained by @Brad-Edwards. The repository has been moved to a new location.

Overview

A Rust library implementing a wide range of algorithms, from fundamental computer science concepts to advanced machine learning techniques.

Implementation Status

✅ Currently Implemented

Sorting Algorithms

✅ QuickSort
✅ MergeSort
✅ HeapSort
✅ BubbleSort
✅ InsertionSort
✅ SelectionSort
✅ ShellSort
✅ CountingSort
✅ RadixSort
✅ Randomized QuickSelect ✅ Randomized QuickSort ✅ BucketSort

Searching Algorithms

✅ Linear Search
✅ Binary Search
✅ Ternary Search
✅ Interpolation Search
✅ Jump Search
✅ Exponential Search
✅ Fibonacci Search
✅ Sublist Search
✅ Depth-First Search
✅ Breadth-First Search

String Algorithms

✅ Knuth-Morris-Pratt (KMP)
✅ Rabin-Karp
✅ Boyer-Moore
✅ Z-Algorithm
✅ Aho-Corasick
✅ Suffix Array Construction
✅ Suffix Automaton
✅ Suffix Tree
✅ Rolling Hash
✅ Manacher's Algorithm

Graph Algorithms (Part 1)

✅ Dijkstra's Algorithm
✅ Bellman-Ford Algorithm
✅ Floyd-Warshall Algorithm
✅ Prim's Algorithm
✅ Kruskal's Algorithm
✅ Tarjan's Algorithm (SCC)
✅ Kosaraju's Algorithm
✅ Johnson's Algorithm
✅ Warshall's Algorithm
✅ Topological Sort

Graph Algorithms (Part 2)

✅ Edmond–Karp (max flow)
✅ Dinic's Algorithm (max flow)
✅ Ford–Fulkerson (max flow)
✅ Hungarian Algorithm (assignment)
✅ Hopcroft–Karp (bipartite matching)
✅ Edmonds' Blossom Algorithm (max matching)
✅ Bron–Kerbosch (maximal clique)
✅ Johnson's Cycle Detection
✅ Floyd's Cycle Detection (Tortoise and Hare)
✅ Euler Tour / Euler Circuit Algorithm
✅ Hierholzer's Algorithm (Euler paths/circuits)
✅ Karger's Min Cut
✅ Randomized Delaunay Triangulation
✅ Randomized Kruskal's MST
✅ Randomized Prim's MST

Dynamic Programming

✅ Kadane's Algorithm
✅ Matrix Chain Multiplication
✅ Edit Distance
✅ Coin Change
✅ Longest Common Subsequence
✅ Longest Increasing Subsequence
✅ Weighted Interval Scheduling
✅ Viterbi Algorithm
✅ Bellman Equation-based DP
✅ Knuth Optimization

Hashing

✅ Perfect Hashing
✅ Universal Hashing
✅ Cuckoo Hashing
✅ Separate Chaining
✅ Open Addressing (linear/quadratic probing, double hashing)
✅ Polynomial Rolling Hash
✅ FNV (Fowler–Noll–Vo) Hash
✅ CRC32
✅ Jenkins Hash
✅ MurmurHash

Classic Machine Learning

✅ k-Means Clustering
✅ k-Nearest Neighbors (k-NN)
✅ Linear Regression (OLS)
✅ Logistic Regression
✅ Decision Tree Learning (ID3, C4.5)
✅ Random Forest
✅ Support Vector Machine (SVM)
✅ Naive Bayes
✅ Gradient Boosting (GBM family)
✅ XGBoost

DO NOT USE Cryptography and Security DO NOT USE

✅ RSA
✅ Diffie–Hellman Key Exchange
✅ ElGamal Encryption
✅ AES (Rijndael)
✅ Blowfish
✅ Twofish
✅ SHA-256
✅ MD5 (legacy)
✅ Elliptic Curve Cryptography (ECC)
✅ DSA (Digital Signature Algorithm)

Deep Learning & Neural Network Training

✅ Backpropagation
✅ Stochastic Gradient Descent (SGD)
✅ Adam Optimizer
✅ RMSProp
✅ AdaGrad
✅ RProp (resilient propagation)
✅ Dropout (regularization)
✅ Batch Normalization
✅ Convolution (core of CNNs)
✅ BPTT (Backprop Through Time, RNNs/LSTMs)

Reinforcement Learning

✅ Q-Learning
✅ SARSA
✅ Double Q-Learning
✅ Deep Q-Network (DQN)
✅ Monte Carlo Exploring Starts
✅ Policy Gradients (REINFORCE)
✅ Actor–Critic Methods
✅ Proximal Policy Optimization (PPO)
✅ Trust Region Policy Optimization (TRPO)
✅ AlphaZero-Style MCTS + RL

Approximation Algorithms

✅ Greedy Set Cover
✅ 2-Approximation for Vertex Cover
✅ PTAS for Knapsack
✅ Christofides' Algorithm (TSP)
✅ Johnson's Algorithm for MAX-SAT
✅ FPTAS for Subset Sum
✅ Local-Ratio Theorem
✅ Primal–Dual Approximation (for covering problems)
✅ LP Rounding (generic approach)
✅ Goemans–Williamson (Max-Cut)

Linear & Nonlinear Optimization

✅ Gradient Descent
✅ Newton's Method
✅ Conjugate Gradient
✅ BFGS
✅ L-BFGS
✅ Simplex Method (linear programming)
✅ Interior Point Method (LP/NLP)
✅ Nelder–Mead
✅ Genetic Algorithm
✅ Simulated Annealing

Integer Linear Programming Methods

✅ Branch and Bound
✅ Branch and Cut
✅ Branch and Price
✅ Gomory Cutting Planes
✅ Dantzig–Wolfe Decomposition
✅ Benders Decomposition
✅ Mixed Integer Rounding Cuts
✅ Lift-and-Project Cuts
✅ Branch & Reduce
✅ Column Generation

Randomized Algorithms

✅ Randomized BFS 2-SAT
✅ Reservoir Sampling
✅ Skip List

Monte Carlo Methods

✅ Monte Carlo Integration

Combinatorial & Backtracking

✅ Backtracking for Permutations/Combinations
✅ Johnson–Trotter (permutation generation)
✅ Gray Code Generation
✅ Knuth's Dancing Links (Algorithm X)
✅ Zassenhaus Algorithm (group factorization)
✅ Hamiltonian Cycle Backtracking
✅ Subset Generation (binary representation)

Data Compression

✅ Huffman Coding
✅ LZ77
✅ LZ78
✅ LZW
✅ Arithmetic Coding
✅ DEFLATE
✅ Burrows–Wheeler Transform (bzip2)
✅ PPM (Prediction by Partial Matching)
✅ LZMA
✅ RANS Coding

Error Correction & Coding

✅ Reed–Solomon Codes
✅ Hamming Codes
✅ Convolutional Codes and Viterbi Decoding
✅ Turbo Codes
✅ LDPC (Low-Density Parity-Check) Codes
✅ CRC (Cyclic Redundancy Check)
✅ BCH Codes
✅ Polar Codes
✅ Fountain / Raptor Codes

Contributing

Contributions are welcome! Please feel free to submit a Pull Request. For major changes, please open an issue first to discuss what you would like to change.

License

This project is licensed under the BSD 3-Clause License - see the LICENSE file for details.