Algorithms.

This repository is a collection of ~20 popular algorithms implemented in Python. It's intended to cover different design paradigms
and if possible, to illustrate problems they solve.

Sorting:

• Selection sort [code]

Basic O(n^2) sorting algorithm.

• Quicksort [code]

An example of "divide and conquer" algorithm with an average O(n log n) complexity.
The implementation provides comparisons counter and pivot selection.

• Merge sort [code]

Another example of "divide and conquer" algorithm. The implementation can monitor a number of inversions.

• Heap sort [code]

There are two versions of this algorithm. The first one takes advantage of heapq library. The second one is a part of heap data structure implementation. That's exactly what makes a difference between this and selection sort algorithms - the heap under the hood.

Extract min/max value:

• Heap [code]

The implementation supports both, min and max heaps. There is also sort method and opportunity to draw a heap to stdout.

    heap = Heap(maxheap=True)  # maxheap
    heap.heapify([1, -2, 3, 18, 2, -8, 12, 4, 5, -6, 9, 3, 2, 0, 45])
    heap.draw(print_width=80)

                                                                                   Level: 0 
                                           45                                       
                                                                                   Level: 1 
                       9                                       18                   
                                                                                   Level: 2 
             4                   5                   3                   12         
                                                                                   Level: 3 
        -2        3         -6        2         -8        2         0         1  

• Median maintenance [code]

Briefly speaking, there are two heaps, min and max. The algorithm do its best to keep a number of elements in each of them equal all the time.
The value "between" heaps is the median.

Minimum spanning tree:

• Prim-Dijkstra-Jarnik MST [code]

It's almost a copy of Dijkstra's shortest path algorithm. They're very similar to each other.

• Kruskal's MST [code]

The implementation is based on union-find (disjoint-set) data structure.

Illustration:

The shortest path:

• Dijkstra shortest path [code]

It's almost a copy of Prim-Dijkstra-Jarnik MST algorithm. They're very similar to each other.

• Bellman-Ford shortest path [code]

Bellman-Ford with negative weight cycle detection.

Illustration:

Other graph algorithms:

• DFS topological sort [code]

Uses depth-first search on a directed acyclic graph. DFS recursive calls and backtracking.

• Breadth-first search BFS [code]

It checks if a graph is connected. It can also count distance (as a number of edges) between nodes.
Works on both, directed and undirected graphs.

• Kosaraju's strongly connected components algorithm [code]

Two runs of DFS. First run traverses the graph and builds a stack of nodes according to finishing times.
Second run traverses the reversed graph in the order of nodes in the stack, sets leaders and groups components.

• Karger's mincut algorithm [code]

Karger's contraction concept is realized as a Monte Carlo type algorithm, that has to be run multiple times
with hope to find minimum cuts, but with no guarantee.

Illustration:

Miscellaneous:

• 2 sum problem [code]

Are there any two numbers in a given list, that create a given sum? Four approaches for solving the problem:
brute force, hashing, binary search and inward walk.

• Huffman codes [code]

Lossless compression based on prefix Huffman codes.

• Knapsack problem [code]

Dynamic programming example, memoization leads to a pretty and effective solution.

• Tasks scheduler [code]

Simple task scheduler based on weight/length ratio. Computes weighted completion time as well.

• Clustering [code]

The algorithm groups items in k clusters. It's based on the "union-find" structure.

Illustration:

Tools:

• Adjacency list [code]

It's just a supporting tool for some of the above graph algorithms.

• Display graph [code]

Another supporting tool. It uses matplotlib and networkx to display results of couple of the above graph algorithms.

Appendix

• If you'd like to learn more about algorithms, data structures, proofs and various theoretical concepts in general, I recommend Tim Roughgarden's classes where you should find a fair and satisfying set of information, that covers all these topics.

• If you find a bug, typo or have any questions, please feel free to contact me.

Contact

abcs.luk@gmail.com

License

MIT