Whenever I face an interesting problem I document the algorithm that I learned to solve it. The goals of this repository is to have clean, efficient and most importantly correct code.
✅: If the algorithm is tested
🔺: If the algorithm is untested
- Knapsack 0/1 O(nC) Bottom-Up implementation (Loops) 🔺
- Knapsack 0/1 O(nC) - Recursive with memoization implementation 🔺
- 🎥Sequence Alignment O(nm) 🔺
- 🎥Weighted Interval Scheduling O(nlog(n)) 🔺
- Kahns Topological Sort - O(n + m) 🔺
- Bellman-Ford Shortest Path - Unoptimized implementation
- Floyd-Warshall Shortest Path - O(n3) 🔺
- Dijkstra Shortest Path - Naive implementation 🔺
- Dijkstra Shortest Path O(mlog(n)) - Heap implementation 🔺
- Karger's Minimum cut - 🔺
- Prim's Algorithm - Naive implementation 🔺
- Prim's Algorithm - mlog(n) 🔺
- Kruskal's Algorithm - Naive implementation 🔺
- Kruskal's Algorithm - mlog(n) 🔺
- Breadth First Search O(n + m) - Queue Implementation 🔺
- Depth First Search O(n + m) - Stack Implementation 🔺
- Depth First Search O(n + m) - Recursive Implementation 🔺
- Karatsuba Multiplication - O(n1.585) 🔺
- Intersection of two sets - O(nlog(n)) + O(mlog(m)) 🔺
- Union of two sets - O(nlog(n)) + O(mlog(m)) 🔺
- Pollard p-1 factorization - 🔺
- Euclidean Algorithm - O(log(n)) 🔺
- Extended Euclidean Algorithm - O(log(n)) 🔺
- Sieve of Eratosthenes - O(nlog(log(n))) 🔺
- Prime factorization - O(sqrt(n)) 🔺
- Ceasar Cipher - 🔺
- Hill Cipher - 🔺
- Vigenere Cipher - 🔺
- One time pad - 🔺
- RSA-Algorithm - 🔺
- Maintaining Median - 🔺
- Huffman Algorithm - 🔺
- 🎥Interval Scheduling - O(nlog(n)) 🔺
- Binary Search - O(log(n)) 🔺
- Bubble sort - O(n2) 🔺
- Hope sort - O(1), hopefully 🔺
- Insertion sort - O(n2) 🔺
- Selection sort - O(n2) 🔺
- Merge sort - O(nlog(n)) 🔺
- Randomized Quick sort - Average O(nlogn) (Input independent!) 🔺
- Quick sort - Average O(nlog(n)) 🔺
I appreciate feedback on potential improvements and/or if you see an error that I've made! Also if you would like to contribute then do a pull request with algorithm & tests! :)