Algorithms-Stanford

Can we do better?… $1,000,000

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

• Introduction, Guiding Principles, and Asymptotic Analysis
• Master Theorem
• Karatsuba Multiplication ( trivial templates )
• Karatsuba Multiplication ( non-trivial strings )
• Merge Sort
• Array Inversions
• Strassen’s Matrix Multiplication
• Closest Pair ( minimal Euclidean distance between two points in a 2-D plane )
• Randomized Quick Sort
• Randomized Linear Selection
• Deterministic Linear Selection
• Karger Minimum Cut ( Randomized Edge Contractions ) < Monte Carlo >

Course 2: Graph Search, Shortest Paths, and Data Structures

• Introduction, Graph Representations, Primitives, and the Web
• Breadth First Search ( BFS )
• Minimum Path Distances ( BFS )
• Depth First Search ( DFS - Iterative )
• Depth First Search ( DFS - Recursive )
• Topological Sort ( DFS )
• Topological Sort ( BFS )
• Undirected Connected Components ( BFS )
• Kosaraju ( DFS + DFS - Recursive )
• Kosaraju ( DFS + DFS - Iterative )
• Dijkstra ( priority queue )
• Heap ( sort + median )
• Search Trees
• Two Sum ( hash table )

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

• Introduction and Motivating Applications
• LRU Cache
• Job Scheduler ( Minimum Weighted Sum of Completion Times )
• Prim ( trivial search in O( N^2 ) time )
• Prim - Minimum Spanning Tree ( MST ) ( non-trivial with heap in O( (M+N)log(N) ) time )
• Kruskal
• Boruvka - Minimum Spanning Tree ( MST ) ( Union-Find + Path Compression )
• Karger, Klein, Tarjan - Randomized Minimum Spanning Forest ( relies on adaptation of Boruvka’s algorithm )
• K-Clustering
• Huffman Coding
• Maximum Independent Set
• Knapsack
• Sequence Alignment ( Needleman-Wunsch score )
• Optimal Binary Search Trees

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

• Introduction, All-Pairs Shortest Paths (APSP), Algorithmic Approaches to NP-Complete Problems
• Bellman Ford
• Bellman Ford ( memory optimized + cycle detection )
• Floyd Warshall
• Floyd Warshall ( memory optimized )
• Floyd Warshall ( memory optimized + transitive closure )
• Johnson
• Vertex Cover ( min K graph )
• Vertex Cover ( min K tree )
• Travelling Salesman
• Travelling Salesman ( heuristic )
• Knapsack ( heuristic )
• Max Cut ( bipartite graph )
• 2-SAT ( Papadimitriou random flips )
• 2-SAT ( Kosaraju SCC )

Supplemental Resources

• Master-Theorem
• Algorithms: Dasgupta-Papadimitriou-Vazirani ( 2006 )
• Algorithms and Data Structures: Mehlhorn-Sanders ( 2007 )
• Introduction to Algorithms: Cormen-Leiserson-Rivest-Stein ( 2009 )
• Discrete Probability
• Mathematical Proofs