/rust-algorithms

Algorithms and data structures implemented in Rust.

Primary LanguageRustMIT LicenseMIT

Algorithms

Repository for my algorithms and data structures implementation (Lists approx. 350 algorithms).

Checked algorithms have been implemented in Rust in "src/respective folder".

Backtracking

  • Crossword Puzzle
  • Hamiltonian Cycle
  • Knight's Tour Problem
  • N Queens Puzzle
  • Subset Sum
  • Sudoku

Combinatorics

  • Binomial Coefficients
  • Burnside's lemma
  • Brent's algorithm
  • Catalan Numbers
  • Fisher-Yates shuffle
  • Floyd's cycle-finding algorithm
  • Gale-Shapley algorithm

Compression

  • Arithmetic Coding
  • Delta Encoding
  • Huffman Coding
  • Lempel-Ziv-Welch algorithm
  • LZ77
  • Run-length encoding
  • Shannon-Fano coding
  • Wavelet Compression

Cryptography

  • Affine Cipher
  • Base16
  • Base32
  • Base64
  • Base85
  • Caesar Cipher
  • Diffie-Hellman Key Exchange
  • Elliptic-curve Diffie-Hellman
  • Hill Cipher
  • Locality Sensitive Hashing
  • RSA Cipher
  • RSA Factorization
  • RSA Key Generator
  • Shuffled Shift Cipher
  • Simple Substitution Cipher
  • Transposition Cipher
  • XOR Cipher

Data Structures

  • Bitset
  • Bloom Filter
  • Hash Table
  • Stack (Dynamic Array Based)

Heap

  • Binomial Heap
  • Fibonacci Heap
  • Min Heap
  • Randomized Heap

Linked List

  • Doubly Linked List
  • Circular Linked List
  • Singly Linked List
  • Skip List

Queue

  • Deque
  • Priority Queue
  • Queue (Dynamic Array Based)

Tree

  • (2,4) tree
  • AVL Tree
  • B Tree
  • Basic Binary Tree
  • Binary Search Tree
  • Fenwick Tree
  • Interval Tree
  • K-d tree
  • Link cut Tree
  • Merkle Tree
  • Quad Tree
  • Red-Black Tree
  • Segment Tree with lazy propagation
  • Splay Tree
  • Sqrt tree
  • Stern-Brocot Tree and Farey sequences
  • Treap/Cartesian Tree
  • van Emde Boas Tree

Union Find

  • Grid Percolation
  • Lowest Common Ancestors using DSU
  • Union Find with path compression

Dynamic Programming

  • Coin Change Problem
  • Coin Row Problem
  • Edit/Levenshtein Distance
  • Fibonacci (Fast Doubling)
  • Fibonacci (Matrix Exponentiation)
  • Fibonacci (Recursion with memoization)
  • Josephus Problem
  • Kadane's algorithm - Maximum Subarray Problem
  • 0-1 Knapsack Problem (Bounded)
  • 0-1 Knapsack Problem (Unbounded)
  • Longest Common Subsequence
  • Longest Common Substring
  • Longest Bitonic Subsequence
  • Longest Increasing Subsequence
  • Longest Palindrome Subsequence
  • Matrix Chain Multiplication
  • Shortest Common Supersequence
  • Subset Sum
  • Wildcard Pattern Matching
  • Word Break Problem

Fast Fourier Transform

  • Bluestein's FFT algorithm
  • Bruun's FFT algorithm
  • Cooley-Tukey algorithm
  • Prime factor FFT algorithm
  • Rader's FFT algorithm

Game Theory

  • Alpha-beta pruning
  • Minimax
  • Sprague-Grundy Theorem
  • SSS-* (State Space Search)

Geometry

  • Angles between vectors (2D, 3D)
  • Centroids
  • Closest Pair of Points
  • Collinear Points
  • Collision detection
  • Cone algorithm
  • Coplanar Points
  • Convex Hull (Chan's algorithm)
  • Convex Hull (Gift wrapping algorithm)
  • Convex Hull (Graham's scan)
  • Convex Hull (Quickhull)
  • Euclidean Distance
  • Geometric hashing
  • Gilbert-Johnson-Keerthi distance
  • Jump-and-Walk algorithm
  • Kirkpatrick-Seidel algorithm
  • Line segment intersection
  • Manhattan Distance
  • Mesh Generation
  • Minimum bounding box algorithm
  • Minkowski sum of convex polygons
  • Nearest Neighbour search
  • Pick's Theorem
  • Point in polygon
  • Point Rotation
  • Shoelace algorithm
  • Sweep line algorithm

Graph Theory

  • A-* Search
  • B-* Search
  • Adjacency List
  • Adjacency Matrix
  • Beam Search
  • Beam stack search
  • Bellman-Ford Shortest Path
  • Best first search
  • Bidirectional search
  • Bipartite Graph Check
  • Breadth First Search
  • Bron-Kerbosch algorithm
  • Christofides algorithm
  • Condensation Graph
  • Depth First Search
  • Detect and find cycles in a graph
  • Dijkstra's Shorted Path
  • D'Esopo-Pape algorithm
  • Edmonds' Algorithm
  • Euclidean shortest path problem
  • Euler Tour
  • Finding articulation points
  • Finding augmenting paths in a flow network
  • Finding bridges
  • Finding negative cycles
  • Floyd-Warshall Shortest Path
  • General Problem Solver
  • Girvan-Newman algorithm
  • Graph Coloring Algorithm
  • Heavy light decomposition
  • Hopcroft-Karp algorithm
  • Hungarian algorithm
  • Hyperlink-Induced Topic Search
  • Isomorphism
  • Iterative deepening DFS
  • Johnson's algorithm for sparse paths
  • Jump point search
  • Karger's algorithm
  • Kirchhoff's theorem
  • Kosaraju's algorithm - strongly connected components
  • Lexicographic BFS
  • Lowest Common Ancestor (Binary Lifting)
  • Lowest Common Ancestor (Farach-Colton and Bender algorithm)
  • Lowest Common Ancestor (Tarjan's off-line)
  • Longest path problem
  • Maximum Bipartite Matching
  • Maximum Flow (Dinic's Algorithm)
  • Maximum Flow (Ford-Fulkerson algorithm)
  • Maximum Flow (Push-relabel algorithm)
  • Minimum Spanning Tree (Kruskal)
  • Minimum Spanning Tree (Prim's)
  • Multifragment Heuristic
  • PageRank
  • Path-based strong components algorithm
  • Prufer coding
  • Strongly Connected Components
  • Subgraph isomorphism problem
  • Tarjan's strongly connected components
  • Topologically sort the nodes of a graph
  • Transitive Closure Problem
  • TrustRank
  • Uniform-cost search
  • Warnsdorff's rule - Knight's tour heuristic

Linear Algebra

  • Biconjugate gradient method
  • Freivalds' algorithm
  • Gaussian Elimination
  • Kraut & Determinant
  • Matrix Inverse
  • Matrix Multiplication - Normal
  • Matrix Transposition
  • Rank of a matrix
  • Strassen Matrix Multiplication
  • Symbolic Cholesky decomposition

Number Theory

  • ACORN Pseudorandom Number Generator
  • Addition chain exponentiation
  • AKS primality test
  • Armstrong Number
  • Baillie-PSW primality test
  • Binary Exponentiation
  • Blum Blum Shub Pseudorandom Number Generator
  • Booth's Multiplication Algorithm
  • Chakravala method
  • Chinese Remainder Problem
  • Collatz Sequence
  • Congruence of squares
  • Coprimality Check
  • Dixon's Algorithm
  • Euler Totient Function
  • Euclid's Algorithm
  • Extended Euclidean Algorithm
  • Factorial Modulo P
  • Factorials (Iterative)
  • Fermat's Factorization method
  • Fermat's Last Theorem
  • Fermat Primality test
  • Finding Full Reptend Primes
  • General Number Field Sieve
  • Karatsuba algorithm
  • Least Common Multiple
  • Lagged Fibonacci Pseudorandom Number Generator
  • Lenstra elliptic curve factorization
  • Linear Congruential Pseudorandom Number Generator
  • Linear Diophantine Equations
  • Logarithmic Exponentiation
  • Lucas primality test
  • Mersenne Twister Pseudorandom Number Generator
  • Modular Multiplicative Inverse
  • Modular Exponentiation
  • Montgomery Multiplication
  • Number of divisors
  • Odlyzko-Schonhage algorithm
  • P-adic valuation
  • Pollard's p - 1 algorithm
  • Pollard's rho algorithm
  • Prime Factors below N
  • Prime Factorizarion
  • Primality Check
  • Primitive Roots
  • Quadratic Sieve
  • Rabin Miller Primality Test (Deterministic)
  • Rabin Miller Primality Test (Probabilisitic)
  • Schonhage-Strassen algorithm
  • Shor's Algorithm
  • Sieve of Atkin
  • Sieve of Eratosthenes
  • Sieve of Sundaram
  • Special Number Field Sieve
  • Sum of Divisors
  • Toom-Cook multiplication
  • Tonelli-Shanks algorithm

Parsing

  • CYK parsing algorihm
  • LL Parsing
  • LR Parsing
  • Pratt Parsing
  • Recursive descent parsing
  • Shunting Yard algorithm

Sorting & Order Statistics

  • Bitonic Sort
  • Bogo Sort
  • Bubble Sort
  • Bucket Sort
  • Burst Sort
  • Comb Sort
  • Counting Sort
  • Cycle Sort
  • Flash Sort
  • Gnome Sort
  • Heap Sort
  • Insertion Sort
  • Introselect
  • Intro Sort
  • K-order statistic
  • Mergesort
  • Odd-even Sort
  • Pigeonhole Sort
  • Quicksort
  • Quickselect
  • Selection Sort
  • Shell Sort
  • Stooge Sort
  • Tim Sort
  • Tree Sort

Strings

  • Aho-Corasick string matching algorithm
  • Boyer-Moore String Search
  • Boyer-Moore-Horpspool String Search
  • Damerau-Levenshtein distance
  • Dice's coefficient
  • Hamming Distance
  • Jaro-Winkler distance
  • Krauss matching wildcards algorithm
  • Knuth-Morris-Pratt algorithm
  • Levenshtein edit distance
  • Longest Common Prefix Array
  • Longest Repeated Substring
  • Lyndon factorization
  • Manacher's algorithm
  • Rabin-Karp string matching algorithm
  • Radix Sort
  • Rich Salz' wildmat
  • String matching with finite automata
  • Suffix Array
  • Suffix Automaton
  • Suffix Tree
  • Trie
  • Ukkonen's algorithm
  • Wavelet tree
  • Z Function
  • Zhu-Takaoka string matching

Miscellaneous

  • 2-SAT
  • Balanced Ternary
  • Binary Search
  • Cellular Automata
  • Dekker's algorithm
  • Doomsday algorithm
  • Easter day algorithms
  • Fibonacci Search
  • Floyd-Rivest algorithm
  • Fractional Knapsack Problem
  • Generating subsets
  • Gray code
  • Hill Climbing Search
  • Hopcroft's algorithm
  • Jump Search
  • Integration by Simpson's Formula
  • Interpolation Search
  • Kleene's algorithm
  • Meet in the middle
  • Mo's algorithm
  • Newton's algorithm for finding roots
  • Powerset construction (aka Rabin-Scott subset construction)
  • Predictive Search
  • Range XOR
  • Simplex Algorithm
  • Simulated Annealing
  • Sqrt decomposition
  • Tabu Search
  • Ternary Search
  • Thompson's construction algorithm
  • Tomasulo algorithm
  • Tracing garbage collection
  • Uniform binary search
  • Xor swap algorithm
  • Zeller's congruence