[Build Status] [License: MIT] [codecov]

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

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