algorithms.py

A port of @sagivo's algorithms in Python 3

Problems

Problem	Solution
Dijkstra's algorithm for finding the shortest path	dijkstra.py
Newton's method for finding the square root of a number	sqrt.py
Binary search algorithm	binary_search.py
Longest increasing subsequence	lis.py
Longest common subsequence	lcs.py
Quicksort	quicksort.py
Mergesort	mergesort.py
Counting sort	counting_sort.py
Shellsort	TODO
Mix and combine sets of cells to list all possible combinations	mix_sets.py
Finding all combinations of well-formed brackets	well_formed_brackets.py
Phonewords	phonewords.py
Permutation	permutation.py
Finding the power set of a given set	power_set.py
Find the next higher number that has the same set of digits	same_digits_next_bigger.py
[Find the minimum insertions needed to form a Palindrome](from http://www.geeksforgeeks.org/dynamic-programming-set-28-minimum-insertions-to-form-a-palindrome/)	palindrome_insertions.py
Knuth–Morris–Pratt algorithm	kmp.py
Conway's Game of Life	game_of_life.py
Knapsack problem	TODO

Goals

• Recursion over imperative looping constructs such as for/while-loops (1)
• Expressions over stateful methods and mutations (whenever possible)

Neither is easy to achive in OO, however, I believe mutability should be opt-in, not the other way around.

Notes:

1. Recursion is not generally considered a good practice in Python. Python is not a functional programming language, and there is no TCO support in CPython after all. The focus here is, in fact, more on the algorithms despite being implemented in Python.

How to run tests

All tests can be found in tests.py. Run the following command to test them.

python -m tests

Versions tested

• Python 3.2
• Python 3.3
• Python 3.4

TODO

• More problems
• Further analysis/optimisation

Contributions

Please feel free to submit an issue or pull request for any bugs you may find or algorithms incorrectly implemented.

License

GNU GPLv3