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(n^{2.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) |