Foundations of Data Science

Avrim Blum is Chief Academic Officer at Toyota Technical Institute at Chicago and formerly Professor at Carnegie Mellon University, Pennsylvania. He has over 25,000 citations for his work in algorithms and machine learning. He has received the AI Journal Classic Paper Award, ICML/COLT 10-Year Best Paper Award, Sloan Fellowship, NSF NYI award, and Herb Simon Teaching Award, and is a Fellow of the Association for Computing Machinery (ACM). John Hopcroft is a member of the National Academy of Sciences and National Academy of Engineering, and a foreign member of the Chinese Academy of Sciences. He received the Turing Award in 1986, was appointed to the National Science Board in 1992 by President George H. W. Bush, and was presented with the Friendship Award by Premier Li Keqiang for his work in China. Ravi Kannan is Principal Researcher for Microsoft Research, India. He was the recipient of the Fulkerson Prize in Discrete Mathematics (1991) and the Knuth Prize (ACM) in 2011. He is a distinguished alumnus of the Indian Institute of Technology, Bombay, and his past faculty appointments include Massachusetts Institute of Technology, Carnegie Mellon University, Pennsylvania, Yale University, Connecticut, and the Indian Institute of Science.

1. Introduction; 2. High-dimensional space; 3. Best-fit subspaces and Singular Value Decomposition (SVD); 4. Random walks and Markov chains; 5. Machine learning; 6. Algorithms for massive data problems: streaming, sketching, and sampling; 7. Clustering; 8. Random graphs; 9. Topic models, non-negative matrix factorization, hidden Markov models, and graphical models; 10. Other topics; 11. Wavelets; 12. Appendix.