CMSC858C, The Probabilistic Method, Spring 2009
Tue, Thu 11 AM - 12:15 PM, CSIC 3118
There will be no required textbook for this course. We will distribute
notes/papers as necessary. Three 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, and
Probability and Computing: Randomized Algorithms and Probabilistic
Analysis by M. Mitzenmacher and E. Upfal,
Cambridge University Press, 2005.
The course will be valid for Ph.D. qualifying coursework,
M.S. qualifying coursework, and M.S. comps, all in the "Algorithms and
Computation Theory" area; the relevant exams will be the
mid-term and the final. In addition to classical material, we will
also cover some of the probabilistic underpinnings of machine learning.
Grading: We will have a take-home mid-term and in-class
final. The grade will be determined by: Homework 25%, Mid-term 25%,
Final 30%, and contribution to Wikipedia 20%.
Enthusiastic participation is strongly encouraged.
Homework: We will have some graded and some ungraded
homework assignments. Students will work in groups of two for all graded
homework assignments, and are also strongly encouraged to complete the
ungraded assignments (solutions to which will be provided).
Exams: The final will be during the university's
official time: in our classroom CSIC 3118, 8-10AM on Thursday, May 14th.
The final will include everything covered during the semester: you
can bring your own notes, HW solutions, and handouts given in class - no
other material is allowed.
The mid-term will be handed out in class on March 24th, and will be
due at the beginning of class on March 31st; it will include all
material covered up to the class of March 12th.
Office Hours: Aravind's office hours will be Tuesday,
Thursday 1-2PM in his office, AVW 3263. If you want to meet him outside
of these periods, please email him to set up a time.
Homework 1, due Feb 17 (Last problem updated: delta only
has to be at least 2)
Ungraded Homework 1
Homework 2, due Mar 17 (Problem 3 updated: |S| is O(n / eps^2);
also, HW2 deadline is now March 17th)
Ungraded Homework 2
Homework 3, due Apr 30
Students claiming a excused absence 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.
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
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)."