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.
- 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))
- 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! :)