Algorithms Collection Python

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

Dynamic Programming

• ✅ Knapsack 0/1 - O(nC) Bottom-Up implementation (Loops)
• ✅ 🎥Sequence Alignment - O(nm)
• ✅ 🎥Weighted Interval Scheduling - O(nlog(n))

Graph theory

• ✅ 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

Mathematics

Algebra

• 🔺 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))

Number Theory

• 🔺 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))

Cryptography

• ✅ Ceasar Cipher
• 🔺 Hill Cipher
• 🔺 Vigenere Cipher*
• 🔺 One time pad
• 🔺 RSA-Algorithm

Numerical Methods

• 🔺 Bisection Method
• 🔺 (simple) Fixpoint iteration

Other

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

Sorting algorithms

• ✅ 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))

Contributing

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