CMSC858S Randomness and Computation, Spring 2007

MWF 10-10:50 AM, CSIC 1121
Instructor: Aravind Srinivasan

Administrative Details

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, Second Edition by N. Alon and J. H. Spencer, Wiley, 2000, and Probability and Computing: Randomized Algorithms and Probabilistic Analysis by M. Mitzenmacher and E. Upfal, Cambridge University Press, 2005.

The course will count for PhD core, MS coursework, and MS comps; for MS comps, the relevant exams will be the mid-term and the final.

The grader for the course is Brent Gordon.

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 30%, scribe notes 10%, and class participation 5%. Enthusiastic participation is strongly encouraged.

Homework: Reading and understanding technical papers well is an important outcome that we aim for. So, in addition to regular homework (each due in about two weeks' time), there will be a few longer-term homework assignments where students will read papers and answer questions based on them. Students will work in groups of two for all homework assignments.

Exams: The final will be during the university's official time: in our classroom CSIC 1121, 8-10AM on Friday, May 18. The final will include everything covered during the semester. You can bring your own notes, the class-notes distributed, HW solutions, project solutions, and handouts given in class; no other material is allowed. Come relaxed!
The mid-term will be take-home: it will be given on March 12th, and will be due at the start of class on March 16th.

Office Hours: Aravind's office hours will be Monday, Wednesday 2-3PM in his office, AVW 3227. If you want to meet him outside of these periods, please email him to set up a time.

Homework and Midterm

Homework 1
Homework 2
Homework 3
Homework 4
Reading Homework 1
Homework 5
Homework 6 (deadline extended to April 25th)
Reading Homework 2
Homework 7

Course Outline

The powerful role played by randomness in computation has been among the central discoveries in the foundations of computer science over the last three decades. This course is an introduction to randomized algorithms and the probabilistic (i.e., average-case) analysis of algorithms. It aims to teach the foundations and some of the several applications of the field. There will be a particular emphasis on applications in networks (social, wireless, peer-to-peer, Web) and distributed algorithms; we also plan to cover applications in learning theory, approximation algorithms, algorithms for massive datasets, and certain other areas as time permits. The main prerequisites will be a strong interest in algorithms and related math, and enthusiasm for teamwork.

We will study some fundamental principles for the design of (de)randomized algorithms: The following are some of the main tools we will use in analyzing randomized algorithms. Not only are these important for analysis: often, a (rough) calculation using such tools of what one might expect from a certain type of randomized algorithm, drives the detailed design of the algorithm. We will illustrate the above techniques and paradigms through applications such as:

Excused Absences

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.

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

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