Classic Algorithms in Rust

This repo contains the implementation of various classic algorithms for educational purposes in Rust. It includes a comprehensive list of algorithms. Contributions are welcome!

The main goal right now is to improve docs, code readability and tests.

Setup

This repo is only for educational purposes. It is meant to be used as a reference material. Thus, it is written as a library instead of a binary.

The way to check the execution of an algorithm is running the tests, which you can do using:

cargo test

Sorting Algorithms

• [x] Bingo
• [x] Bitonic
• [x] Bogo Bogo
• [x] Bogo
• [x] Bubble
• [x] Bucket
• [x] Cocktail-Shaker
• [x] Comb
• [x] Counting
• [x] Cycle
• [x] Exchange
• [x] Gnome
• [x] Heap
• [x] Insertion
• [x] Merge
• [x] Odd-even
• [x] Pancake
• [x] Pigeonhole
• [x] Quick
• [x] Radix
• [x] Selection
• [x] Shell
• [x] Sleep
• [x] Stooge
• [x] Strand
• [x] Timsort
• [x] Tree

Graphs

• [x] Bellman-Ford
• [x] Breadth-First Search (BFS)
• [x] Centroid Decomposition
• [x] Depth First Search (DFS)
• [x] Dijkstra
• [x] Dinic's Max Flow
• [x] Heavy Light Decomposition
• [x] Kruskal's Minimum Spanning Tree
• [x] Lowest Common Ancestor
• [x] Prim's Minimum Spanning Tree
• [x] Prufer Code
• [x] Tarjan's Strongly Connected Components
• [x] Topological sorting

Dynamic Programming

• [x] 0-1 Knapsack
• [x] Coin Change
• [x] Edit Distance
• [x] Egg Dropping Puzzle
• [x] Is Subsequence
• [x] K-Means Clustering
• [x] Longest common subsequence
• [x] Longest continuous increasing subsequence
• [x] Longest increasing subsequence
• [x] Maximal Square
• [x] Maximum Subarray
• [x] Rod Cutting

Data Structures

• [x] AVL Tree
• [x] B-Tree
• [x] Binary Search Tree
• [x] Fenwick Tree
• [x] Graph
  • [x] Directed
  • [x] Undirected
• [x] Heap
• [x] Hashtable
• [x] Linked List
• [x] Queue
• [x] RB Tree
• [x] Segment Tree
• [x] Stack using Linked List
• [x] Stack
• [x] Trie
• [x] Union-find

Strings

• [x] Aho-Corasick Algorithm
• [x] Burrows-Wheeler transform
• [ ] Finite Automaton
• [x] Hamming Distance
• [x] Knuth Morris Pratt
• [x] Manacher
• [x] Naive
• [x] Rabin Carp
• [x] Reverse

General

• [x] Convex Hull: Graham Scan
• [x] Graph Coloring
• [x] Huffman Encoding
• [x] Kmeans
• [x] N-Queens Problem
• [x] Tower of Hanoi
• [x] Two Sum

Ciphers

• [x] Caesar
• [x] Morse Code
• [x] Polybius
• [x] SHA-2
• [x] TEA
• [x] Transposition
• [x] Vigenère
• [x] XOR
• Rot13
  • [x] Another Rot13
  • [x] Rot13

Bit Manipulation

• [x] Bit Distance
• [x] Bit Equivalence
• [x] Clear Bit
• [x] Count Ones
• [x] Divide By Two
• [x] Get Bit
• [x] Is Even
• [x] Is Positive
• [x] Is Power Of Two
• [x] Multiply By Two
• [x] Multiply Signed
• [x] Multiply Unsigned
• [x] Rightmost 1-bit
• [x] Rightmost 0-bit
• [x] Set Bit
• [x] Twos Complement
• [x] Update Bit

Geometry

• [x] Closest pair of 2D points

Search

• [x] Binary Search Recursive
• [x] Binary Search
• [x] Exponential
• [x] Fibonacci
• [x] Jump
• [x] Kth Smallest
• [x] Linear
• [x] Quick Select
• [x] Ternary Search Min Max Recursive
• [x] Ternary Search Min Max
• [x] Ternary Search Recursive
• [x] Ternary Search

Math

• [x] Armstrong Number
• [x] Baby-Step Giant-Step Algorithm
• [x] Derivative
• [x] Extended euclidean algorithm
• [x] Fast Fourier Transform
• [x] Fast power algorithm
• [x] Gaussian Elimination
• [x] Greatest common divisor of n numbers
• [x] Greatest common divisor
• [x] Karatsuba Multiplication Algorithm
• [x] Least common multiple of n numbers
• [x] Linear Sieve
• [x] Miller Rabin primality test
• [x] Pascal's triangle
• [x] Perfect number
• [x] Permuted Congruential Random Number Generator
• [x] Pollard's Rho algorithm
• [x] Prime factors
• [x] Prime number
• [x] Quadratic Residue
• [x] Simpson's Rule for Integration
• [x] Square root with Newton's method
• [x] Trapezoidal Integration
• [x] Zeller's Congruence Algorithm

Contributing

See CONTRIBUTING.md