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.
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/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

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)