Reading

Lecture Notes

Reference Books and Notes

[Er] J. Erickson, Algorithms, self-published, 2019.
[Er2] J. Erickson, More Algorithms Lecture Notes, self-published, 2019.
[DVP] S. Dasgupta, U. Vazirani, C. Papadimitriou, Algorithms, McGraw-Hill, 2006.
[Ed] H. Edelsbrunner, Design and Analysis of Algorithms, lecture notes, 2008.
[KT] R. Kleinberg, È. Tardos, Algorithm Design, Pearson, 2009.
[MRS] C. D. Manning, P. Raghavan, H. Schütze, An Introduction to Information Retrieval, Cambridge University Press, 2008.
[MG] J. Matoušek and B. Gärtner, Understanding and Using Linear Programming, Springer, 2007.
[MR] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press.
[WS] D. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.

Ranking, Sorting, and Summarization

[AV] A. Aggarwal, J. S. Vitter, The Input/Output Complexity of Sorting and Related Problems, Commun. ACM 31(9) (1988): 1116-1127
[BCELP] F. Brandt, V. Conitzer, E. Endriss, J. Lang, A. D. Procaccia, Handbook of Computational Social Choice, Cambridge University Press, 2016.
[DKNS] C. Dwork, R. Kumar, M. Naor, D. Sivakumar, Rank Aggregation Methods for the Web, WWW Conference 2001: 613-622.
[GK] M. Greenwald, S. Khanna, Space-Efficient Online Computation of Quantile Summaries, SIGMOD Conference 2001, 58-66.
[MP] J. I. Munro, M. Paterson, Selection and Sorting with Limited Storage, Theor. Comput. Sci. 12: 315-323, 1980.

Graphs: shortest paths & similarity

[ADFGW] I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, R. F. Werneck, Highway Dimension and Provably Efficient Shortest Path Algorithms, Journal of the ACM 63.5 (1-26), 2016.
[NBK] E. Nikolova, M. Brand, D. Karger, Optimal Route Planning under Uncertainty, ICAPS, 2006.
[SM] J. Setubal, J. Meidanis, Introduction to Computational Molecular Biology, PWS Publishing Company, 1997.

Clustering

[XT] D. Xu, Y. Tian, A Comprehensive Survey of Clustering Algorithms, Annals of Data Science 2 (165-193), 2015.
[JMF] A. K. Jain, M. N. Murty, P. J. Flynn, Data Clustering: A Review, ACM Computing Surveys 31.3 (264-323), 1999.
[Na] V. Nagarajan, Local search, lecture notes, 2021.
[Bh] A. Bhaskara, Local search and gradient descent, lecture notes, 2018.
[VL] U. von Luxburg, A tutorial on spectral clustering, Stat Comput 17:395-416, 2007.
[Sp] D. Spielman, Spectral and Algebraic Graph Theory, self-published, 2019.

Graphs: Flows, cuts, matchings

[MSVV] A. Mehta, A. Saberi, U. Vazirani, V. Vazirani, AdWords and generalized online matching, Journal of the ACM 54.5, 2007.
[Kl] R. Kleinberg, Bipartite Maximum Matching, lecture notes, 2016.
[St] C. Stein, Hopcroft-Karp Bipartite Matching Algorithm and Hall’s Theorem, lecture notes, 2012.

Optimization

[Go] M. Goemans, Linear Programming, lecture notes, 2015.
[La] M. Lavrov, Integer Programming Methods, lecture notes, 2020.
[Ka] S. Kakade, Gradient Descent and Stochastic Gradient Descent, lecture notes, 2016.
[Gr] R. Grosse, Optimization, lecture notes, 2020.
[Go2] M. Goemans, Ellipsoid Algorithm, lecture notes, 2017.
[Te] T. Terlaky, An easy way to teach interior-point methods, European Journal of Operational Research 130, 2001.

Hashing

[BM] A. Broder, M. Mitzenmacher, Network Applications of Bloom Filters: A Survey, Internet Mathematics Vol. 1, No. 4: 485-509, 2004.
[MS] B. Maggs, R. Sitaraman, Algorithmic Nuggets in Content Delivery, ACM SIGCOMM Computer Communication Review, Vol 45 Issue 3, 2015.
[RV] T. Roughgarden, G. Valiant, Consistent Hashing, lecture notes, 2021.
[CM] G. Cormode, S. Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch and its Applications, Journal of Algorithms, Vol 55 Issue 1 58-75, 2005.
[HP] S. Har-Peled, Geometric Approximation Algorithms, AMS, 2011.
[AI] A. Andoni, P. Indyk, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Commun. ACM 51(1): 117-122, 2008.
[GIM] A. Gionis, P. Indyk, R. Motwani, Similarity Search in High Dimensions via Hashing, VLDB: 518-529, 1999.