CS 574: Randomized Algorithms, Fall 2025


Course Summary

Basic 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 Information

Lectures: 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.
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
University wellness center
Please do not hesitate to contact the instructor if you need help or assistance.

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

  • Lecture 1: 8/27/2025, Introduction, Randomized Quick Sort, Markov'e inequality, Max-Cut
    • Tablet notes
    • Randomized Quick Sort is covered in all books/notes
    • Additional reading: Randomized Quick Selection, Reverse Markov Inequality

  • Lecture 2: 8/29/2025, Karger's random contraction for min-cut, Karger-Stein variation
    • Tablet notes
    • Motwani Raghavan Chapter 1, Aspens/Sariel/Kent notes
    • Additional reading: Galton-Watson process (wikipedia), some notes
    • David Karger's influential thesis

  • Lecture 3: 9/03/2025, Polynomial Identity Testing, Schwartz-Zippel Lemma, Applications to Matchings

  • Lecture 4: 9/05/2025, Chebyshev and Chernoff bounds, applications to max load in balls and bins etc
    • Tablet notes
    • Slides from a previous course
    • Chapter 4 of Motwani-Raghavan book or Mitzenmacher/Upfal book, Chapter 5 of Aspnes notes, Chapter 13 of Sariel's notes, ...
    • Sariel Har-Peled's Chernoff cheat sheet