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.

:white_check_mark:: If the algorithm is tested
:small_red_triangle:: If the algorithm is untested

Dynamic Programming

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

Graph theory

• :white_check_mark: Kahns Topological Sort - O(n + m)
• :white_check_mark: Bellman-Ford Shortest Path - O(mn)
• :small_red_triangle: Floyd-Warshall Shortest Path - O(n³)
• :white_check_mark: Dijkstra Shortest Path - Naive implementation
• :white_check_mark: Dijkstra Shortest Path - O(mlog(n)) - Heap implementation
• :small_red_triangle: Karger's Minimum cut
• :small_red_triangle: Prim's Algorithm - O(mn) Naive implementation
• :white_check_mark: Prim's Algorithm - O(mlog(n)) Heap implementation
• :small_red_triangle: Kruskal's Algorithm - O(mn) implementation
• :white_check_mark: Kruskal's Algorithm - O(mlog(n))
• :white_check_mark: Breadth First Search - O(n + m) - Queue Implementation
• :white_check_mark: Depth First Search - O(n + m) - Stack Implementation
• :white_check_mark: Depth First Search - O(n + m) - Recursive Implementation

Mathematics

Algebra

• :small_red_triangle: Karatsuba Multiplication - O(n^1.585)
• :white_check_mark: Intersection of two sets - O(nlog(n)) + O(mlog(m))
• :white_check_mark: Union of two sets - O(nlog(n)) + O(mlog(m))

Number Theory

• :small_red_triangle: Pollard p-1 factorization
• :small_red_triangle: Euclidean Algorithm - O(log(n))
• :small_red_triangle: Extended Euclidean Algorithm - O(log(n))
• :small_red_triangle: Sieve of Eratosthenes - O(nlog(log(n)))
• :small_red_triangle: Prime factorization - O(sqrt(n))

Cryptography

• :white_check_mark: Ceasar Cipher
• :small_red_triangle: Hill Cipher
• :small_red_triangle: Vigenere Cipher*
• :small_red_triangle: One time pad
• :small_red_triangle: RSA-Algorithm

Numerical Methods

• :small_red_triangle: Bisection Method
• :small_red_triangle: (simple) Fixpoint iteration

Other

• :white_check_mark: Maintaining Median - O(nlog(n))
• :small_red_triangle: Huffman Algorithm
• :white_check_mark: :movie_camera:Interval Scheduling - O(nlog(n))
• :white_check_mark: Binary Search - O(log(n))

Sorting algorithms

• :white_check_mark: Bubble sort - O(n²)
• :small_red_triangle: Hope sort - O(1), hopefully
• :white_check_mark: Insertion sort - O(n²)
• :white_check_mark: Selection sort - O(n²)
• :white_check_mark: Merge sort - O(nlog(n))
• :white_check_mark: Randomized Quick sort - Average O(nlogn) (Input independent!)
• :white_check_mark: 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! :)