Algorithms Collection Python

Whenever I face an interesting problem I document the algorithm that I learned to solve it. Hopefully my list will increase as time goes on.

Dynamic Programming

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

Graph theory

• Kahns Topological Sort - O(|V|+|E|)
• Bellman-Ford Shortest Path - Unoptimized implementation
• Floyd-Warshall Shortest Path - O(n³)
• Dijkstra Shortest Path - Naive implementation
• Dijkstra Shortest Path O(|E| + |V|log|V|) - Heap implementation
• Karger's Minimum cut
• Prim's Algorithm - Naive implementation
• Prim's Algorithm - Heap implementation
• Kruskal's Algorithm - Naive implementation
• Kruskal's Algorithm - Union Find implementation
• Breadth First Search O(|V| + |E|) - Queue Implementation
• Depth First Search O(|V| + |E|) - Stack Implementation
• Depth First Search O(|V| + |E|) - 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
• 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!