| 1/10 | Review of asymptotic notation, Master Theorem, sorting, matrix multiplication |
| 1/12 | FFT, easy and hard problems Read Section 2 of Edmonds. Paths, trees, and flowers. 1963. |
| 1/17 | Karp. Reducibility among combinatorial problems. 1972. (Kathryn) |
| 1/19 | History of fast matrix multiplication |
| 1/24 | Winograd. A new algorithm for inner product. 1968. Strassen. Gaussian Elimination is not optimal. 1969. Bini, Capovani, Romani, and Lotti. O(n2.7799) complexity for n × n approximate matrix multiplication. 1979. (Koby) |
| 1/26 | Sequential memory models and blocked matrix multiplication |
| 1/31 | Frigo, Leiserson, Prokop, and Ramachandran. Cache-oblivious algorithms. 1999. (Sajant) |
| 2/2 | Graph algorithms |
| 2/7 | Park, Penner, and Prasanna. Optimizing graph algorithms for improved cache performance. 2004. (Bel) |
| 2/9 | Parallel memory models |
| 2/14 | Aggarwal, Chandra, and Snir. Communication complexity of PRAMs. 1990. *Sections 1-3 only! (Gabe) |
| 2/16 | NO CLASS |
| 2/21 | McColl and Tiskin. Memory-efficient matrix multiplication in the BSP model. 1999. (Becky) |
| 2/23 | MPI and collectives
FW Programming Assignment Due |
| 2/28 | Chan, Heimlich, Purkayastha, and van de Geijn. Collective communication: theory, practice, and experience. 2007. (Edward) |
| 3/2 | Project Proposals Due
NO CLASS |
| 3/7 | Spring Break |
| 3/9 | Spring Break |
| 3/14 | Irony, Toledo, and Tiskin. Communication lower bounds for distributed-memory matrix multiplication. 2004. (Kanika) |
| 3/16 | Matrix computations |
| 3/21 | Ballard, Carson, Demmel, Hoemmen, Knight, and Schwartz. Communication lower bounds and optimal algorithms for numerical linear algebra. 2014. *Section 2 only! (Bruce) |
| 3/23 | Low-rank approximations |
| 3/28 | Zhou, Wilkinson, Schreiber, and Pan. Large-scale parallel collaborative filtering for the Netflix Prize. 2008. (Matt) |
| 3/30 | Nearest neighbor and related problems |
| 4/4 | Andoni and Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. 2008. (Riana) |
| 4/6 | Review day |
| 4/11 | Project Presentations (Kathryn/Koby) |
| 4/13 | Project Presentations (Gabe) |
| 4/18 | Project Presentations (Becky/Kanika) |
| 4/20 | Project Presentations (Matt/Edward&Bel) |
| 4/25 | Project Presentations (Sajant/Riana) |