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
Mid-term
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 first moment method / linearity of expectation / union bound.
- The second moment method.
- Alteration.
- Random sampling.
- Randomly ordering the data.
- Hashing and fingerprinting.
- Derandomization: the method of conditional probabilities,
k-wise independence and k-wise "almost independence";
applications to hashing, fingerprinting
and sketching.
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.
- Linearity of expectation, union bound, truncated
inclusion-exclusion.
- Large-deviation bounds:
- the bounds of Markov, Chebyshev, Chebyshev-Cantelli, Chernoff,
and Hoeffding;
- exploiting negative correlation and ``near-independence'';
- Martingale tail bounds.
- The FKG and Janson inequalities, and the Poisson paradigm;
- The Lovász Local Lemma.
- A brief look at further tail bounds: Kim-Vu, Vu, Janson-Rucinski.
- A peek into quantum mechanics and quantum computing.
We will illustrate the above techniques and paradigms
through applications such as:
- Efficient packet-routing in arbitrary networks
- Dealing with malicious users in peer-to-peer and other network models
- Connections between random graphs, social networks,
and peer-to-peer networks
- Wireless networks (sensor, ad hoc, mesh): information dissemination,
energy conservation, estimating throughput capacity
- Fundamental tasks in learning theory
- Summarizing large data-sets, and algorithms for data streams
- Approximation algorithms in combinatorial optimization
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
http://www.shc.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)."