/Algorithms-and-Data-Structure

Here are some algorithms and data structures written by Python. [Finished!]

Primary LanguagePython

Algorithms-and-Data-Structure

Here is the list of all algorithms and data structures, seperated into a few categories, according to the course of Stanford on coursera - Algorithms Specialization.

Part1. Divide and Conquer, Sorting and Searching, and Randomized Algorithms

1.1 Asymptotic Analysis

  • Recursive Algorithm for multiplication of two integers
  • Karatsube Algorithm for multiplication of two integers
  • Merge Sort

1.2 Devide & Conquer Algorithms, the Master Method

  • Devidde and Conquer counting inversions

1.3 Quick Sort Algorithm

  • Quick Sort (first element as pivot)
  • Quick Sort (last element as pivot)
  • Quick Sort (median of three numbers as pivot)
  • Quick Sort (random pivot)

1.4 Linear-time Selection, Graphs, the Contraction Algorithm

  • Karger Min Cut Algorithm

Part2. Graph Search, Shortest Paths, and Data Structures

2.1 BFS and DFS

  • Computing SCCs (Strongly Connected Components) using Iteration
  • Computing SCCs using Recursion (this version works not well on a large data set)

2.2 Dijkstra's Shortest Path Algorithm

  • Dijkstra's Algorithm (using brute-force)
  • Dijkstra's Algorithm (using heap)

2.3 Heap and Tree

  • MinHeap (e.g. Median Maintenance)
  • Red Black Tree

2.4 Hash Table and Bloom Filter

  • Hash Table
  • Bloom Filter

Part3. Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

3.1 Greedy Algorithm and Prim's MST

  • Job Scheduling using Greedy Algorithm
  • Prim's MST using brute-force/heap

3.2 Kruskal's MST and Clustering

  • Clustering using Kruskal Algorithm with Union Find Set
  • Clustering of big graph (together with Hamming Distance and Bit Operation)

3.3 Huffman Coding and Weighted Independent Set

  • Huffman Coding (using heap)
  • maximum WIS using DP

3.4 Dynamic Programming

  • Knapsack Problem using DP (smaller problem)
  • Knapsack Problem using recursiong with memorization (bigger problem)
  • Sequence Alignment/Edit Distance
  • Optimal Binary Search Tree

Part4. Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

4.1 The Bellman-Ford Algorithm and All-Pairs Shortest Paths

  • APSP Problem with Floyd Warshall Algorithm

4.2 NP-Complete Problems and Faster Exact Algorithsm for NPC Problems

  • TSP Problem with DP (using Bitmask for acceleration)

4.3 Approximation Algorithms for NPC Problems

  • TSP Problem with Nearest Neighbor heuristic

4.4 Local Search Algorithms

  • 2-SAT Problem with Papadimitriou's Algorithm with optimization