Repository files navigation

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)
• ✅🎥Sequence Alignment- O(nm)
• ✅🎥Weighted Interval Scheduling- O(nlog(n))

• ✅Kahns Topological Sort- O(n + m)
• ✅Bellman-Ford Shortest Path- O(mn)
• 🔺Floyd-Warshall Shortest Path- O(n³)
• ✅Dijkstra Shortest Path- Naive implementation
• ✅Dijkstra Shortest Path- O(mlog(n)) - Heap implementation
• 🔺Karger's Minimum cut
• 🔺Prim's Algorithm- O(mn) Naive implementation
• ✅Prim's Algorithm- O(mlog(n)) Heap implementation
• 🔺Kruskal's Algorithm- O(mn) implementation
• ✅Kruskal's Algorithm- O(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(n^1.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

• 🔺Bisection Method
• 🔺(simple) Fixpoint iteration

• ✅Maintaining Median- O(nlog(n))
• 🔺Huffman Algorithm
• ✅🎥Interval Scheduling- O(nlog(n))
• ✅Binary Search- O(log(n))

• ✅Bubble sort- O(n²)
• 🔺Hope sort- O(1), hopefully
• ✅Insertion sort- O(n²)
• ✅Selection sort- O(n²)
• ✅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! :)