CMSC651, Analysis of Algorithms, Spring 2024
Instructor: Aravind
Srinivasan
Class Venue and Time: CSI 1122, TuTh 9:30AM - 10:45AM
tl;dr -- Students: please add
yourselves to the Piazza page for
the class! We will use Piazza extensively.
Administrative Details
Instructor:
Aravind
Srinivasan
Office: IRB 4204, Phone: 301-405-2695
Instructor's Office Hours: Tue, Thu 11AM--noon at IRB 4204, or by
appointment (please email Aravind)
TA:
Nitya Raju (nraju AT umd)
TA Office Hours and Location: Nitya Raju: Wed 1PM-2PM (open area on the 5th floor of Iribe near IRB 5136), or by appointment
Course Time and Location: Tue, Thu
9:30AM-10:45AM, CSI 1122
Course Webpage:
https://www.cs.umd.edu/class/spring2024/cmsc651.
Study Resources
There will be no required textbooks; some key online resources will be
posted here, and additional ones will also be posted on Piazze. The class will
also have a partly "flipped-classroom" format: some amount of additional
learning will be from papers and videos that we will review in class.
Some of the key resources include the following--we include these with
many thanks to the authors/presenters:
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. My 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 (mine 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.
Course Overview
The times allocated below are
approximate and changeable subject to class interest.
Randomized algorithms and the probabilistic method (6 lectures)
Exact algorithms for hard problems (including fixed-parameter tractability) (1 lecture)
Approximation algorithms, algorithmic proof of LP duality by approximation; advanced examples--approximation as well as exact algorithms--of dynamic programming, divide-and-conquer, greedy algorithms, and local search (6 lectures)
Combinatorial optimization: separation orcales and randomized meta-rounding, matching, matroids, submodularity, iterative rounding, tree metrics (6 lectures)
A very quick tour of basic complexity classes, IP and interactive proofs, the PCP Theorem (Dinur's approach without proof) and consequences for the hardness of approximation (0.5 lecture)
Data-stream algorithms and some lower-bound techniques (1.5 lecture)
Basic algorithms in machine learning (1.5 lecture)
Online algorithms, online learning, and multiplicative weights update (2 lectures)
Spectral methods and continuous algorithms (e.g., for maximum flow) (2 lectures)
A brief look at quantum algorithms (0.5 lecture)
Additional material planned for homework and classes: Basic information theory, parallel algorithms, algorithms with predictions, stochastic optimization, algorithmic fairness, and computational epidemiology (1 lecture)
Grading, Homework, and Exams
The grading will be as follows:
- Homework: 35% (with the lowest score dropped)
- Midterm exam: 25%
- Final exam: 35%
- Participation: 5% (drop by Aravind's office hours at least once)
Course Evaluation
Students are strongly encouraged to complete their course evaluations;
please do so at the CourseEvalUM
website when it is ready.
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 class or by email, a letter of accommodation from the Office of Disability Support
Services (DSS) within the first two weeks of the semester.
Excused Absences, Academic Integrity, and Additional Info.
The policy on excused absences is at https://www.ugst.umd.edu/V-1.00(G).html.
Please see the university's policies on various important issues.
Mandatory Reporting
Notice of mandatory reporting of sexual assault, sexual harassment, interpersonal violence, and stalking: As a faculty member, Aravind Srinivasan is
designated as a "Responsible University Employee", and must report all disclosures of sexual assault, sexual harassment, interpersonal violence, and stalking to UMD's Title IX Coordinator per University
Policy on Sexual Harassment and Other Sexual Misconduct.
If you wish to speak with someone confidentially, please contact one of UMD's confidential resources,
such as CARE to Stop Violence
(located on the Ground Floor of the Health Center) at 301-741-3442 or the
Counseling Center (located at the Shoemaker Building)
at 301-314-7651.
You may also seek assistance or supportive measures from UMD's Title IX Coordinator,
Angela Nastase, by calling 301-405-1142, or emailing titleIXcoordinator@umd.edu.
To view further information on the above, please visit the
Office of Civil Rights and Sexual Misconduct's website.
Web Accessibility