CS 574: Randomized Algorithms, Fall 2025Course SummaryBasic and advanced concepts in the design and analysis of randomized algorithms. Sampling; concentration inequalities such as Chernoff-Hoeffding bounds; probabilistic method; random walks, dimension reduction; entropy; martingales and Azuma's inequality; derandomization. Randomized algorithms for sorting and searching; graphs; geometric problems. Basics of pseudorandomness and randomized complexity classes. The actual contents will vary a bit from semester to semester. Administrative InformationLectures: 9.30-10.45am on Wed and Fri. Siebel Center 0216.Instructor: Chandra Chekuri, 3228 Siebel Center, (chekuri at) Office Hours (Chandra): Friday 1-2pm in 3228 Siebel, or by appointment Teaching Assistant: Rhea Jain (rheaj3 at) Office Hours (Rhea): Tuesday 2-3pm, Siebel lower level (open whiteboard area) Grading Policy: 50% Homework (5 biweekly), 2 x 15% Midterms, 20% final project Attendance policy: at least 65% of lectures for a grade. The revolution will not be televised, it will be live. Prerequisites: According to the course catalog: one of CS 473, CSE 414, or MATH 473; and one of MATH 461, MATH 463 or STAT 400. Or equivalent courses from elsewhere. Consult the instructor if you have questions. 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. Student code: All students are expected to be aware of the university's student code, in particular the academic integrity policies CS Code of Conduct: See here for important information on the code of conduct guidelines of the Siebel School of CS. References Electronic versions of several books from Cambridge University, Springer, Wiley and other publishers are available free to Univ of Illinois students via the library.
Ed (sign up at link), Gradescope (7X756Y)Homework Lectures
|