A collection of common algorithms.
| Algorithm | Wikipedia | time-complexity |
|---|---|---|
| Dynamic Programming | ||
| knapsack.py | Knapsack problem | O(n ⋅ W) |
| edit_distance.py | Edit distance | O(n ⋅ m) |
| bellman_ford.py | Bellman-Ford | O(n ⋅ m) |
| sieve_of_eratosthenes.py | Sieve of Eratosthenes | O(n ⋅ log log n) |
| robot_paths.py | / | O(n²) |
| subset_sum.py | Subset sum problem | O(n ⋅ W), pseudo-polynomial |
| alarm_problem.py | / | O(n) |
| snakes_on_a_grid.py | / | O(n ⋅ m) |
| Greedy Algorithms | ||
| dijkstra.py | Dijkstra's algorithm | O(n²) |
| kruskal.py | Kruskal's algorithm | O(m log m) |
| huffman.py | Huffman coding | O(n log n) |
| interval_scheduling.py | Interval scheduling | O(n log n) |
| Network-Flow Algorithms | ||
| edmonds_karp.py | Edmonds-Karp | O(n ⋅ m²) |
| Other | ||
| gale_shapley.py | Gale-Shapley | O(n²) |
| check_bipartiteness.py | Bipartite graph | O(n + m) |
Disclaimer 1: Each algorithm uses its own data-structures, even when they are identical to those of other algorithms. Thats on purpose.
Disclaimer 2: Of course there might be errors or erroneous behaviour on edge-cases. I tested to some extend, but not exhaustingly.
Disclaimer 3: The complexities given in the table are mostly the complexities of the flavour of implementation, not necessarily the actual complexity for my specific implementation. Therefore actual runtimes might stray from the given ones.
Disclaimer 4: Invokation of algorithms always assumes well-formed input, there is no input-validation (syntactically or semantically) whatsoever.