Algorithms Specialization

This repository contains slides and implementations of the Algorithms Specialization offered by Stanford University on Coursera.

1. Divide and Conquer

The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts). Application examples

1. Karatsuba
2. MergeSort
3. Counting Inversions
4. QuickSort
5. Karger (Contraction Algorithm For MinCuts)

2. Graph Search

The topics in this part on the specialization are: data structures (heaps, balanced search trees, hash tables, bloom filters), graph primitives (applications of breadth-first and depth-first search, connectivity, shortest paths), and their applications (ranging from deduplication to social network analysis). Application examples

1. Breadth First Search (Layers and Shortest Path)
2. Deep First Search
3. Strongly Connected Components with Korasaju's algorithm
4. Dijkstra's Shortest Path Algorithm
5. Median Maintenance Using Heaps
6. Two Sum Problem With Hashset

3. Greedy Algorithms

This part covers the several subjects: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees). Application examples

1. Schedule jobs using a greedy algorithm
2. Prim's Minimum Spaninng Tree
3. Greedy Clustering Algorithm
4. Huffman Code
5. Maximum Weighted Independent Sets with dynamic programming
6. Knapsack problem with bottom-up dynamic programming approach

4. Shortest Paths Revisited

Finally the topics in this part are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search). Application examples

1. Floyd-Warshall algorithm on all-pairs shortest path problem
2. NP-Complete Problems
3. Traveling Salesman Problem with Dynamic Programming
4. Traveling Salesman Problem with heuristic greedy algorithm