Algo_stanford

This repository contains Coursera Stanford Algorithm Specialization implementations in Python.

Course 1: Divide and Conquer, Sorting and Searching, and Randomized Algorithms

Divide and Conquer Algorithms

1. Karastuba's Integer Multiplication
2. Merge Sort
3. Count Inversions

Randomized Algorithms

4. Count Quick Sort Comparisons
5. Karger's Minimum Cut Algorithm

Course 2: Graph Search, Shortest Path and Data Structures

Graph Search and Shortest Path

1. Strongly Connected Components
2. Dijkstra's Shortest Path Algorithm

Data Structures

3. Median Maintenance using heaps
4. Brutal force implementation of Two Sum problem using hashset
5. Fast implementation of Two Sum problem using sorted array and other tricks

Course 3: Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

Greedy Algorithms

1. Schedule jobs using a greedy algorithm
2. Prim's Minimum Spaninng Tree
3. Greedy Clustering Algorithm
4. Huffman Code

Dynamic Programming

5. Maximum Weighted Independent Sets with dynamic programming
6. Knapsack problem with bottom-up dynamic programming approach.

Course 4: Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

All-pairs Shortest Path

1. Floyd-Warshall algorithm on all-pairs shortest path problem

NP-Complete Problems

2. Traveling Salesman Problem with Dynamic Programming
3. Traveling Salesman Problem with heuristic greedy algorithm