CMSC 858C, Randomized Algorithms, Spring 2023

CMSC 858C, Randomized Algorithms, Spring 2023

Administrative Details

Instructor: Aravind Srinivasan
Office: IRB 4164, Phone: 301-405-2695
Instructor's office Hours: Tue, Thu 2-3 in IRB 4164 (additional slots by appointment; Aravind is happy to talk to students)
Course Time and Location: Tue, Thu 9:30-10:45AM, IRB 2207
TA: Nathaniel Grammel (ngrammel AT umd), office hours Mon, Wed 12-1 (IRB 5230)
Course Webpage: https://www.cs.umd.edu/class/spring2023/cmsc858C/index.html

tl;dr -- Students: please add yourselves to the Piazza page for the class! We will use Piazza extensively.

Course Details

Since this is an advanced graduate class, part of the syllabus will be tailored to the interests of the class, and to the questions that arise in class. The approximate syllabus (part of which will be developed in the homework) includes:

Major paradigms underlying randomized algorithms and the probabilistic method;
A variety of approaches to, and settings for, large-deviation bounds;
The Lovász Local Lemma;
Randomized graph embeddings and decompositions;
Applications in data science, data streams, computational epidemiology, differential privacy, and AI fairness;
Topics in information theory, correlation inequalities, negative dependence, and applications of these as time permits.

There will be no required textbook for this course; we will distribute notes for a good part of the class, with students studying these notes at home and with many classes devoted to problem-solving after a quick recap of the notes. Four excellent books in this field are:

Randomized Algorithms by R. Motwani and P. Raghavan, Cambridge University Press, 1995;
The Probabilistic Method, Third Edition by N. Alon and J. H. Spencer, Wiley, 2008;
Probability and Computing: Randomized Algorithms and Probabilistic Analysis by M. Mitzenmacher and E. Upfal, Cambridge University Press, 2005; and
Concentration of Measure for the Analysis of Randomized Algorithms by D. P. Dubhashi and A. Panconesi, Cambridge University Press, 2009.

Grading: We will have a take-home mid-term and in-class final. The grade will be determined by: Homework 40%, Mid-term 25%, and Final 35%. Enthusiastic participation is strongly encouraged.

Homework and Handouts: Students will work in groups of three for all homework assignments. Please ensure that you typeset your homework in LaTeX. You can find many templates online, and here is one.

Some basic inequalities

Exams: The final will be during the university's official time: in our classroom IRB 2207, 8-10AM on Monday, May 15th. The mid-term will be take-home: date to be announced. The final will cover all concepts covered in class; you can bring your own notes and any notes handed out.

General Info: Class participation is strongly encouraged; students are urged to come to the office hours if they have questions, and can also email Aravind to setup alternative times if they cannot attend the regular office hours. A few lectures will be rescheduled (or covered by guest lectures) during Aravind's travel; very few of the office hours may also be canceled. (Again, students are always welcome to email Aravind to setup additional meeting-times as needed---discussions with students are among the high points of his day!)

Excused Absences

See the university's policy on medically-necessitated absence from class. The "Major Scheduled Grading Events" for this course are the mid-term and final exams; students claiming an excused absence from these events must apply in writing and furnish documentary support (such as from a health-care professional who treated the student) for any assertion that the absence qualifies as an excused absence. The support should explicitly indicate the dates or times the student was incapacitated due to illness. Self-documentation of illness is not itself sufficient support to excuse the absence. An instructor is not under obligation to offer a substitute assignment or to give a student a make-up assessment unless the failure to perform was due to an excused absence.

Academic Accommodations for Disabilities

Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.

Academic Integrity

The University of Maryland, College Park has a nationally recognized Code of Academic Integrity, administered by the Student Honor Council. This Code sets standards for academic integrity at Maryland for all undergraduate and graduate students. As a student you are responsible for upholding these standards for this course. It is very important for you to be aware of the consequences of cheating, fabrication, facilitation, and plagiarism. For more information on the Code of Academic Integrity or the Student Honor Council, please visit http://www.studentconduct.umd.edu.

To further exhibit your commitment to academic integrity, remember to sign the Honor Pledge on all examinations and assignments: "I pledge on my honor that I have not given or received any unauthorized assistance on this examination (assignment)."

Aravind's pledge to the students

Your education is very important to me, and I respect each of you regardless of how you do in the class. The expectations of you are that you attend class and pay full attention, and give enough time to the course. I strongly encourage you to ask questions in class, and to come to the office hours (the instructor's or the TA's) with any further questions. We can have a very enjoyable educational experience if you pay attention in class, give sufficient time to our course, and bring any difficulties you have promptly to our attention. I look forward to our interaction both inside and outside the classroom.

Back to the Department of Computer Science Class Pages

Web Accessibility