# Learn Data Structure and Algorithms by Python

> You need to have basic understanding of the Python programming language to proceed with the codes from this repository.
> Python 3 is used for the implementation of the data structures and Algorithms

## Table of Contents

* [Introduction to Python](#introduction)
* [Data Structure](./Data%20Structure/)
    * [Linked List](./Data%20Structure/Linked%20List/)
    * [Stack](./Data%20Structure/Stack/)
    * [Queue](./Data%20Structure/Queue/)
    * Binary Search Tree (BST)
    * [Heap](./Data%20Structure/Heap/)
    * Hash Table
    * Disjoint Set Union (Union Find)
    * Trie
    * Suffix Array
    * Segment Tree
    * Binary Indexed Tree (BIT)
    * Heavy Light Decomposition

- [Searching](./Searching/)
    * [Linear Search](./Searching/Linear%20Search/)
    * [Binary Search](./Searching/Binary%20Search/)
    * [Ternary Search](./Searching/Ternary%20Search/)

* [Sorting](./Sorting/)
    * Selection Sort
    * [Bubble Sort](./Sorting/Bubble%20Sort/)
    * Insertion Sort
    * Merge Sort
    * Quick Sort
    * Bucket Sort
    * Counting Sort
    * Heap Sort
    * Radix Sort

- Graph Algorithms

    * Graph Representation
    * Breadth First Search (BFS)
    * Depth First Search (DFS)
    * Topological Sort
    * Strongly Connected Components (SCC)
    * Minimum Spanning Tree (MST)
    * All Pairs Shortest Path (Floyd Warshall's Algorithm)
    * Single Source Shortest Path Algorithm
        * Djkastra's Algorithm
        * Bellman Ford Algorithm
    * Directed Acyclic Graph
    * Bipartite Matching
    * Articulation Point, Bridge
    * Euler Tour/Path
    * Hamiltonian Cycle
    * Stable Marriage Problem
    * Chinese Postman Problem
    * 2-satisfiability
    * Flow Algorithms
        * Maximum Flow
        * Minimum Cut
        * Min-Cost Max Flow
        * Maximum Bipartite Matching
        * Vertex Cover

- Dynamic Programming
    * Rod Cutting
    * Maximum Sum (1D, 2D)
    * Coin Change
    * Longest Common Subsequence
    * Longest Increasing Subsequence
    * Matrix Multiplication
    * Edit Distance (Levenshtein distance)
    * 0/1 Knapsack
    * Travelling Salesman Problem
    * Optimal Binary Search Tree

* Greedy Algorithms
    * Activity Selection/Task Scheduling
    * Huffman Coding
    * Knapsack Problem (Fractional Knapsack)

- String Algorithms
    * Rabin-Karp Algorithm
    * Knuth-Morris-Pratt Algorithm
    * Z Algorithm
    * Aho-Korasick Algorithm
    * Manachers Algorithm
    * Boyr-Moore Algorithm

* Number Theory
    * Greatest Common Divisor (GCD)
    * Longest Common Multiplier (LCM)
    * Euler Totient (Phi)
    * Primality Testing
    * Prime finding(Sieve of Eratosthenes)
    * Prime factorization
    * Factorial
    * Fibonacci
    * Counting, Permutation, combination
    * Exponentiation
    * Big Mod
    * Euclid, Extended euclid
    * Josephus Problem
    * Farey Sequence
    * Catalan numbers
    * Burnside's lemma/circular permutation
    * Modular inverse
    * Probability
    * Chinese Remainder Theorem
    * Gaussian Elimination method
    * Dilworth's Theorem
    * Matrix Exponentiation

- Computational Geometry
    * Pick's Theorem
    * Convex hull
    * Line Intersection
    * Point in a polygon
    * Area of a polygon
    * Line Sweeping
    * Polygon intersection
    * Closest Pair

* Game Theory

    * Take Away Game
    * Nim's Game
    * Sprague-grundy Number

* Others
    * BackTracking
        * N-Queen's Problem
    * [Tower of Hanoi Problem](./Others/Tower%20of%20Hanoi/)

---

## Introduction

### Big-O Notation and Time Complexity Analysis

[Algorithms in plain English: time complexity and Big-O notation](https://medium.freecodecamp.com/time-is-complex-but-priceless-f0abd015063c)

[Big-O Cheat Sheet Link](http://bigocheatsheet.com/)

### How to Use

Install Python 3.x in your machine [from here](https://www.python.org/downloads/release/python-343/) (if it's already not installed) and add it to your environment path so that it is accessible in terminal commands.

Then you can run a Python file like this:

```python
python file.py
```

or

```python
python3 file.py
```

### Useful Links:

* [Algorithms, 4th Edition (book by: Robert Sedgewick and Kevin Wayne)](http://algs4.cs.princeton.edu/home/)
* [Khan Academy tutorial on Algorithms](https://www.khanacademy.org/computing/computer-science/algorithms)
* [Topcoder Tutorials](https://www.topcoder.com/community/data-science/data-science-tutorials/)
* [GeeksforGeeks](http://www.geeksforgeeks.org/)
* [hackerearth Tutorial](https://www.hackerearth.com/practice/)