Algos in Python

Implementations of a few algorithms and datastructures for fun and profit!

Completed

  • Karatsuba Multiplication
  • Basic Sorting
  • Counting Inversions in an array
  • Selecting ith order statistic in an array
  • Graph datastructure (directed & undirected)
  • Graph Algos
    • Topological Sorting
    • Shortest hops
    • DFS
    • BFS
    • Connected Components
    • Dijkstra's Shortest Path - O(mlogn)
    • Prim's Minimum Cost Spanning Tree - O(mlogn)
    • Kruskal's Minimum Spanning Tree - O(mlogn)
    • Max k Clustering
    • Bellman Ford
    • Floyd Warshall
    • Johnson's Algorithm
  • Heap datastructure
    • Max heaps
    • Min heaps (priority queue)
    • Heapsort
  • Job Scheduling
  • UnionFind Data Structure
  • Binary Search Tree
  • Kandane's Algorithm
  • Knapsack Problem (0/1 and unbounded)
  • Prefix Tries
  • Stack ADT (with example problems)
    • String Reverse
    • Parenthesis Matching
    • Infix to Postfix

Tests

python -m tests.graph_test
python -m tests.digraph_test
python -m tests.graph_algorithms_test
python -m tests.heap_test
python -m tests.unionfind_test