Skip to content

Latest commit

 

History

History
52 lines (48 loc) · 1.28 KB

README.md

File metadata and controls

52 lines (48 loc) · 1.28 KB
Raw

Algos in Python

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

Completed

  • Karatsuba Multiplication
  • Basic Sorting
  • Rabin-Miller primality test
  • Sieve of Eratosthenes for prime numbers
  • Binary Search
  • 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
python -m tests.singly_linked_list_test