Lectures and References
Lecture 1 (4/7): Introduction to Parallel Algorithms (PRAM Model, Work + Depth, Computation DAGs, Brent's Theorem, Parallel Summation) Lecture 1 Lecture 2 (4/9): Scalability, Scheduling, All Prefix Sum Reading: BB 5. Lecture 2, Handbook of Scheduling, Graham's Algorithm, TensorFlow Scheduling, Better Bounds for Online Scheduling Lecture 3 (4/14): All Prefix Sum, Mergesort. Reading: KT 5, BB 8. Lecture 3, Cole's parallel merge sort (1988) Lecture 4 (4/16): Divide and Conquer Algorithms, Master Theorem, Quick Selection, Quick Sort. Lecture 4Lecture 5 (4/21): Quicksort, Matrix Multiplication (Strassen's Algorithm), Minimum Spanning Tree (Kruskal's Algorithm). Reading: KT 3, 4.5, 4.6. Lecture 5, Linear time bounds for median select, Prefix scan qsort Lecture 6 (4/23): Minimum Spanning Tree (Boruvka's Algorithm). Reading: CLRS 12, 13. Lecture 6, Boruvka (1926) Lecture 7 (4/21): Solving Linear Systems, Intro to Optimization. Lecture 7. Lecture 8 (4/28): Optimization for Machine Learning, HOGWILD!. Lecture 8., HOGWILD!, Omnivore. Lecture 9 (4/30): Midterm Review Lecture 10 (5/5): Midterm (In Class). Lecture 11 (5/12): Introduction to Distributed Algorithms, Communication Networks, Cluster Computing, Broadcast Networks, and Communication Patterns Lecture 11, Communication Patterns Lecture 12 (5/14): Distributed Summation, Simple Random Sampling, Distributed Sort. Lecture 12 Lecture 13 (5/19): Introduction to MapReduce, Sparse Matrix Multiplication using SQL, Sparse Matrix Multiplication in MapReduce. Lecture 13 Sparse matrix multiplication using SQL, Sparse matrix multiplication in MapReduce. Lecture 14 (5/21): Triangle Counting in MapReduce, Introduction to Spark and RDDs Lecture 14, Curse of the Last Reducer, Intro to Spark, Intro to Distributed Optimization Lecture 15 (5/26): Partitioning for PageRank; Optimization, Scaling, and Gradient Descent in Spark Lecture 15, Partitioning for Pagerank. Lecture 16 (5/28): Matrix Operations, and Singular Value Decomposition in Spark. Lecture 16, Singular Value Decomposition. Lecture 17 (6/2): Covariance Matrices and All-pairs similarity Lecture 17, Covariance Matrices and All-pairs similarity. Lecture 18 (6/4): TBD. Lecture 19 (6/9): Final