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

Machine Learning

• Apriori Algorithm
• AdaBoost
• C4.5 algorithm
• CART (Classification and Regression Tree)
• Chi-square automatic interaction detection (CHAID)
• Eclat Algorithm
• Genetic Algorithm
• Hidden Markov Model
• Histogram of Oriented Gradients
• ID3 algorithm
• K-means Clustering
• K Nearest Neighbours
• Linear Discriminant Analysis
• Linear Regression
• Logistic Regression
• Markov Chains
• Monte Carlo Tree Search
• Partial Least Squares Regression
• Polynomial Regression
• Principal Component Analysis
• Random Forest Classifier
• Random Forest Regressor
• Q Learning
• Self organizing map
• Stemming algorithm
• Support Vector Machine

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