icodein / implementations_of_various_algorithms_and_data_structures Goto Github PK

This contains the implementations of various algorithms and data structures taught in the course by Stanford university, on coursera.
This contains the following algorithms / data structures:
1. Karatsuba integer multiplication algorithm.
2. Mergesort with counting inversions.
3. Closest pair of points on a plane
*. Strassen's Matrix multiplication algorithm.
4. Quicksort and ith order statistic.
5. Karger's minimum cut algorithm with union-find data structure.
6. BFS and DFS
7. Fibonacci Nth term with/without matrix exp.
8. Segment tree
9. Heap
10. Convex Hull, naive implementation
11. Fast Modular exponentiation
12. Sieve of Eratosthenes for generating primes (now linear time).
13. N-dimensional Vectors
13. Prim's Minimal spanning tree algorithm
14. Algorithm to find Suffix array of a string
15. hash table using open addressing
16. Rabin Miller deterministic primality test
17. fast modular multiplicative inverse
18. Matrix library
19. Extended Euclidean algorithm to find modular multiplicative inverse
20. Knuth Morris Pratt string matching algorithm
21. Z algorithm for string matching
22. Square-root decompositon for range sum queries.
23. Binary search tree (with insert, delete, search, print)
24. Union Find (Disjoint Set Union) with union by rank and path compression.

* : Yet to be added.