This course will describe some algorithmic techniques developed for handling large amounts of data that is often available in limited ways. Topics that will be covered include data stream algorithms, sampling and sketching techniques, and sparsification, with applications to signals, matrices, and graphs. Emphasis will be on the theoretical aspects of the design and analysis of such algorithms.
This version of the course is directed at senior level undergraduate students and beginning graduate students, and hence will not assume background in randomized algorithms. The pace of the course and the topics will be commensurately adjusted. The previous edition of this course will give a good idea of the topics to be covered although there will be some changes.
Prerequisites: CS 374 and CS 361, or comparable understanding and facility with algorithms and probability.
Instructor: Chandra Chekuri (3228 Siebel Center, chekuri at illinois.edu).
Teaching assistant: Manuel Torres (manuelt2 at illinois.edu)
Lectures etc: schedule page for logistics, slides, videos, and references.
Zoom office hours: Chandra (Tues, Fri 3.30-4.30pm, Zoom link); Manuel (Mon 1.00-2.00pm, Zoom link)
Announcements: Piazza; Enrollment is required. Almost all announcements will be made on Piazza.
Homework/project submission: Gradescope (self-enrollment code: 92XK44)
Grading policy: 40% Homework (4-5 biweekly), 2 x 20% Midterms, 20% final project
Covid-19 and mental health support at UofI: Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University’s resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.
Counseling Center: 217-333-3704, 610 East John Street, Champaign, IL 61820
McKinley Health Center: 217-333-2700, 1109 South Lincoln Avenue, Urbana, Illinois 61801
Please do not hesitate to contact the instructor if you need help or assistance.
College of Engineering Syllabus Statements: See here for important information and regulations regarding academic integrity, disability accommodations, FERPA rights, religious observances, and sexual misconduct reporting.
Anti-racism and inclusivity: We will strive to make the course a welcoming and encouraging learning environment that is free of bias. Please bring any concerns on these issues to the attention of the instructor or report directly to Bias Assessment and Response Team (BART) (https://bart.illinois.edu/). Be kind, respectful, and professional to everyone and expect the same from others.