chaitya62/procookbook

All the Famous algorithms you need!

ProCookbook

A social exploration of the inner workings of algorithms and data structures.

Overview

ProCookbook is designed to help software engineers engage with algorithms and data structure in a tangible way. It began as a curiosity, and now can be a library of known algorithms.

What this is intended to be

• A python package wrapping up C++ implementations of algorithms.
• A place for you to contribute new algorithms and learn with others.

What this isn't

• A replacement for python's standard libraries.
• A place to copy/paste from TheAlgorithms project.

How to Get Involved

If you would like to help with wrapping the project using the Python-C API, join the discussion on this issue.

List of Algorithms

• Sorting
• Graph/Tree
  • Not Catagorized
• Number Theory
• Data Structures
• Resources
• Useful Sites
• Courses
  • Introduction courses
  • Advance Courses
• Wish List
• Data Structures
• Algorithms

Sorting

The following is a resource for various sorting techniques with their execution time.

1. Bubble Sort 										[Execution time : 199.22 seconds ]  
2. Selection Sort									[Execution time : 75.192 seconds ]  
3. Insertion Sort									[Execution time : 52.833 seconds ]  
4. Shell Sort										[Execution time : 15.703 seconds ]  
5. Merge Sort										[Execution time :  0.86  seconds ]  
6. Quick Sort (without shuffling)					[Execution time :  0.817 seconds ]  
7. Count Sort										[Execution time :  0.645 seconds ]  

Graph/Tree

Tree is special form of graph i.e. minimally connected graph and having only one path between any two vertices. In graph there can be more than one path i.e. graph can have uni-directional or bi-directional paths (edges) between nodes.

1. Graph API
2. Depth first search
3. Breadth first search
4. Dijkstra's Algorithm
5. Floyd-Warshall's Algorithm
6. Lowest common Ancestor
7. Heavy Light Decomposition (create and query only)

Not Catagorized

1. Merge Sort (Incomplete trying inplace mergesort) | READ

Number Theory

1. GCD | wiki | Euclidean Algorithm | Extended Euclidean

2. Sieve of Eratosthenes | wiki | tutorial | Examples

3. Karatsuba's multiplication

4. Miller-Rabin Test for prime numbers

5. Euler's totient function

Data Structures

1. Stack
2. Trie
3. Union Find | Tutorial
4. Fenwick Tree Tutorial
5. Linked List (Add more features)
6. Interval Trees

Resources

Useful Sites

• VisuAlgo
• HackerRank
• Codeforces
• CodeChef
• TopCoder
• e-maxx - for Russian readers
• e-maxx - for English readers

Courses

Introduction courses

• MIT 6.006 Introduction to Algorithms, Fall 2011
• MIT 6.046J Design and Analysis of Algorithms, Spring 2015

Advance Courses

• Advanced Algorithms (COMPSCI 224), Harvard University
• MIT 6.851 Advanced Data Structures, Spring 2012

Wish List

Data Structures

1. Queues
2. Binary Search Tree (All variants)
3. Linked Lists
4. Maps
5. Priority Queue
6. Tries
7. Bag
8. Segment Tree
9. Fenwick Tree
10. HLD on Trees
11. Stacks
12. Skip Lists
13. Interval trees

Algorithms

1. Knuth-Morris-Pratt Algorihm(KMP) | Wiki | Tutorial | Example
2. Rabin-Karp Algorithm | Wiki | Tutorial | Example
3. Dijkstra's Algorithm(shortest Path) | Wiki | Tutorial
4. Floyd Warshall Algorithm Wiki | Tutorial
5. Sparse Table(RMQ)
6. Lowest Common Ancestor Wiki | Tutorial
7. Modular Exponentiation Wiki | Tutorial
8. Counting inversion Wiki | Tutorial
9. Euclid's Extended Algorithm Wiki | Tutorial
10. Knapsack problem Wiki | Tutorial
11. Aho-Corasick String Matching Algorithm Wiki | Tutorial
12. Strongly connected Components Wiki | Tutorial
13. Union-Find Wiki | Tutorial
14. Bellman Ford Algorithm Wiki | Tutorial
15. Convex Hull Wiki | Tutorial
16. K-d tree Wiki | Tutorial
17. Manacher's Algorithm Wiki | Tutorial
18. Sweep Line Algorithm Wiki | Tutorial
19. Stable Marriage Problem Wiki | Tutorial
20. Detecting Cycles in a Graph Wiki | Tutorial
21. Backtracking Wiki | Tutorial
22. Graph Coloring Wiki | Tutorial
23. Johnson's Alogrithm Wiki | Tutorial
24. Link Cut tree Wiki | Tutorial | Video
25. Burnside Lemma Wiki | Tutorial
26. Mo's Algorithm Wiki | Tutorial
27. Minimum Spanning Tree Wiki | Tutorial
28. FFT Wiki | Tutorial
29. Towers of hanoi Wiki | Tutorial
30. Heavy Light Decomposition Wiki | Tutorial
31. Suffix Tree Automation(Pattern Searching) Wiki | Tutorial
32. Binary Indexed Tree Wiki | Tutorial
33. Z Algorithm Wiki | Tutorial
34. Line Intersection Algorithm Wiki | Tutorial
35. Topological Sorting Wiki | Tutorial
36. Binary Search Wiki | Tutorial
37. Hash Function Wiki | Tutorial
38. Segment Trees(Lazy Propagation) Wiki | Tutorial
39. Vertex Cover Problem Wiki | Tutorial
40. Interval Tree Wiki | Tutorial
41. Hungarian Algorithm Wiki | Tutorial
42. Matrix Exponentiation Wiki | Tutorial
43. Gaussian Elimination Wiki | Tutorial
44. Pollard Rho Integer Factorisation Wiki | Tutorial
45. Eulerian and Hamiltonian Path Wiki | Wiki2 | Tutorial
46. Blossom/Edmond's Algorithm Wiki | Tutorial
47. Meet in the middle Wiki | Tutorial
48. Constructive Algorithm Wiki

procookbook's Issues

Add More Algos to the wishlist in readme.markdown

Add new Alogtihms to the wishlist also include links to resources if any.

Write a better README.md

Currently, the readme.md is just a list of algorithms, but as I want this repository to be a python package in the future. A better readme, which explains that and what is in the repository is necessary.

Priority Queue

Add an implementation of priority queue from scratch in CPP

Hashing Algorithm

Create a class or function that hashes various object.

Note: Possible research needed on various hashing algorithm.

Add resources to beside the algorithms

Add usefull resources which help in understanding and implementing the algorithms

Skip Lists

Add an implementation of skip lists in CPP

Convert ProCookbook into a python library

This seems like a huge task, but all issues and small PR contributing to this cause are welcomed.
Some things I think will be needed to be done :

1. Write a python-C++ wrapper to wrap C++ algorithms in python
2. Refactor all algorithms and have a specific framework to write new algorithms in.
3. Write a setup.py to actually wrap it into a python library

This is not an exhaustive list of the task necessary to complete the task of making a python library out of this repository,

Feel free to add new points below or opening the issues for the same.

Add example problems for algorithms

Problems for each algorithm that everyone can solve to learn and implement the algorithm.