CMSC 858C, Randomized Algorithms, Spring 2015 (Aravind Srinivasan)

CMSC 858C, Randomized Algorithms, Spring 2015: Tue, Thu 12:30-1:45PM

Administrative Details

Instructor: Aravind Srinivasan
Office: AVW 3263, Phone: 301-405-2695
Instructor's office Hours: Tue 10-11 and Thu 11-12 in AVW 3263 (additional slots by appointment; Aravind is happy to talk to students)
Course Time and Location: Tue, Thu 12:30-1:45PM, CSIC 2120
Half-TA: David G. Harris
Course Webpage: http://www.cs.umd.edu/class/fall2011/cmsc858C-0101/index.html

Approximate schedule: Please see the topics covered here. Some major paradigms underlying the utility of randomization are marked in green.

There will be no required textbook for this course; we will distribute notes/papers as necessary. 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.

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.

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

Homework and Handouts: We will have some graded and some ungraded homework assignments. Students will work in groups of three for all graded homework assignments, and are also urged to complete the ungraded assignments (solutions to which will be provided).

Some basic inequalities
Homework 1, due Feb 14th
Homework 2, due March 3rd
Homework 3, due March 15th
Mid-term exam, due Apr 12th
Project, due May 8th
Homework 4, due May 11th (This is a shorter HW than usual.)

Exams: The final will be during the university's official time: in our classroom CSIC 2120, 1:30-3:30PM on Tuesday, May 19th. 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 April 2nd, and will be due on April 7th. [This is a little later than planned, due to the FOCS deadline (Apr 2) that quite some of the students will be busy with.]

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.)

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)."

Web Accessibility