This course page is under construction. More details will be added later.
Course Description: With the advent of social networks, ubiquitous sensors, and large-scale computational science, data scientists must deal with data that are massive in size, arrive at blinding speeds, and often must be processed within interactive or quasi-interactive time frames. This course studies the mathematical foundations of big data processing, developing algorithms and learning how to analyze them. We explore methods for sampling, sketching, and distributed processing of large scale databases, graphs, and data streams for purposes of scalable statistical description, querying, pattern mining, and learning. 3 credits.
Prerequisites: The undergraduate prerequisites are COMPSCI 240 or STAT 515 (Probability) and COMPSCI 311 (Algorithms). This is a theoretical course with an emphasis on algorithm design, correctness proofs, and analysis. Aside from a general background in algorithms, a strong mathematical background, particularly in linear algebra and probability is required. If you are a masters student with a limited background in either of these subjects, please email me at the start of the semester to discuss your preparation.
Textbooks: This is no official textbook for this class. We will use some material from the following books:
Foundations of Data Science, Avrim Blum, John Hopcroft and Ravi Kannan.
Mining of Massive Datasets, Jure Leskovec, Anand Rajaraman and Jeff Ullman.
Probability and Computing, Michael Mitzenmacher and Eli Upfal.
Readings from these books and other sources will be posted before class.
Related Classes: You may also find some helpful reference material in these similar classes:
The Modern Algorithmic Toolbox, taught by Gregory Valiant at Stanford.
Sketching Algorithms for Big Data, taught by Piotr Indyk and Jelani Nelson at MIT and Harvard.
COMPSCI 514 last year (Fall 2024), taught by Cameron Musco.
Learning Objectives:
Students will learn about modern tools for data processing, including random sampling and hashing, low-memory streaming algorithms, linear and non-linear dimensionality reduction, spectral graph theory, and continuous optimization. A major goal is to be familiar at a high level with a breadth of algorithmic tools beyond combinatorial algorithms, which are the main focus of most undergraduate algorithms courses.
Through problem sets, students will develop the ability to apply and modify these algorithmic tools to tackle new problems, beyond those discussed in class. They will strengthen their ability to think creatively about algorithmic problems and push beyond known approaches, to develop solutions of their own.
Through assessments that emphasize formal proofs, students will strengthen their ability to formulate problems mathematically and analyze them rigorously.
Through algorithmic problems, students will practice applying fundamental tools in probability theory and linear algebra, which are broadly applicable in data science and machine learning. These include concentration bounds and methods for decomposing complex random variables, eigendecomposition, orthogonal projection, important matrix identities, and fundamentals of high-dimensional geometry and random matrix theory.